\documentclass{article}
\pagestyle{empty}

\begin{document}
\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Fall 2001}\\
\vspace{.3 in}
{\large Assignment 3}
\end{center}

\noindent
This assignment is due at the start of class on Wednesday, Sept. 19.  You may collaborate
in small groups with your classmates to complete this assignment but you should reference your collaborators.  You
also must thoroughly understand any solutions you submit 
and must do your own write-up of those solutions.  You may not refer to solutions
to assignments given in previous semesters of CS140.  This assignment is worth 50 points (25 points if handwritten).  


\vspace{.2 in}

\begin{enumerate}

\item
Prove that the expected running time of Quicksort is $O(n \lg n)$.
Note:  we did much of the proof in lecture but you should reiterate
those steps with your own explanation.


\item
Here is an inductive "proof" that $n^2 = O(n)$.

Clearly $1^2=O(1)$.  Now suppose that $(n-1)^2 = O(n-1)$.  Then
\begin{displaymath}
n^2 = (n-1)^2 +2n -1 = O(n-1) + 2n -1 = O(n).
\end{displaymath}

What is wrong with this "proof."  Hint:  try to replicate the proof
using the defintion of $O(n)$ explicitly.
\end{enumerate}

\end{document}



