\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.

The running time on input of size $n$ is
\begin{displaymath}
T(n) = cn + T(M) + T(n-M-1) 
\end{displaymath}
where $M$, a random variable, is size of the set $S_1$.
Since expectation is linear and $n$ is not random we can write
\begin{displaymath}
E[T(n)] = cn + E[T(m) + T(n-m-1)] 
\end{displaymath}
We can condition the expectation  as follows
\begin{displaymath}
E[T(n)] = cn + E[T(M) + T(n-M-1)]  = cn + \sum_{i=0}^{n-1} 
E[T(M) + T(n-M-1) | M=i) Pr(M=i) = cn +  \sum_{i=0}^{n-1}E[T(i) + T(n-i-1)]Pr(M=i)
\end{displaymath}
The probability that $M=i$ is just the probability that the pivot chosen
has rank $i+1$ (under our assumption that the integers in $S$ are distinct).
Thus
\begin{displaymath}
E[T(n)] = cn + \frac{1}{n} \sum_{i=0}^{n-1} E[T(i) + T(n-i-1)]$
\end{displaymath}

Since $E[T(i)]]$ is an increasing function of $i$ we can bound
this term as
 
\begin{displaymath}
E[T(n)] = cn + \frac{1}{n} \sum_{i=0}^{n-1} E[T(i) + T(n-i-1)]
\le  cn + \frac{2}{n} \sum_{i=0}^{n-1} E[T(max(i, n-i-1)]
\le  cn + \frac{2}{n} \sum_{i=\lfloor (n-1)/2 \rfloor}^{n-1} E[T(i)]
\end{displaymath}

Assume $E[T(i)] \le a \lg (i) + b $ for all $i \le n$.
Then
\begin{displaymath}
E[T(n)] 
\le  cn + \frac{4}{n} \sum_{i=\lfloor (n-1)/2 \rfloor}^{n-1} E[T(i)]
\le  cn + \frac{4}{n} \sum_{i=\lfloor (n-1)/2 \rfloor}^{n-1} (a \lg(i) +b)
\le  cn + \frac{4}{n} \sum_{i=\lfloor (n-1)/2 \rfloor}^{n-1} (a \lg(i) +b)




\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.

Recalling the definition of $O(\cdot)$, we want to
prove that there exist constants $c,M$ such that for every
$n \ge M$, $n^2 \le cn$.  What we actually prove is that
for every $n$ there exists a constant $c$ such that $n^2 \le cn$.
This is, in fact true, but not what we are trying to prove!
\end{enumerate}

\end{document}



