\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\myif}{{\bf if}}
\newcommand{\myelse}{{\bf else}}
\newcommand{\ret}{{\bf return}}
\newcommand{\for}{{\bf for}}
\newcommand{\SS}{\mbox{{\sc Stooge-Sort}}}
\newcommand{\POWER}{\mbox{{\sc Power}}}

\head{3390}{Analysis of Algorithms}{21 October 1998}{9}

\begin{center}
\Large{\bf Sample Solutions for Problem Set 1}
\end{center}

\bigskip

{\noindent {\bf 1 (Problem 2--4(d)).}} False.  We show that there exist
functions $f(n)$ and $g(n)$ such that $f(n) = O(g(n))$ and $2^{f(n)} \neq
O(2^{g(n)})$.

Let $f(n) = n$ and $g(n) = n/2$.  Clearly, $f(n)$ and $g(n)$ are
asymptotically positive functions, as required.  Moreover, since
$0 \le f(n) \le 2 g(n)$ for all $n \ge 1$, we have $f(n) = O(g(n))$.
The functions $2^{f(n)}$ and $2^{g(n)}$ are equal to $2^n$ and $2^{n/2}$,
respectively.  

We now show by contradiction that $2^n \neq O(2^{n/2})$.  Let, if possible,
$2^n = O(2^{n/2})$.  We thus have positive constants $c$ and $n_0$ such that
$2^n \le c 2^{n/2}$ for all $n \ge n_0$.  This implies that $c \ge 2^{n/2}$
for all $n \ge n_0$.  If we set $n$ to be equal to $\max\{n_0, 2\lg c + 2\}$, we
obtain that:
\begin{eqnarray*}
c \ge 2^{n/2} \ge 2^{(2\lg c + 2)/2} = 2^{\lg c + 1} = 2c,
\end{eqnarray*}
which contradicts the fact that $c$ is positive.  Therefore, $2^n \neq
O(2^{n/2})$, and the desired claim holds.

{\noindent {\bf 1 (Problem 2--4(g)).}} False.  We prove that there exists a
function $f(n)$ such that $f(n) \neq \Theta(f(n/2))$.  Let $f(n) = 2^n$.  Then,
$f(n/2) = 2^{n/2}$.  From the part above, it follows that $f(n) \neq
O(f(n/2))$.  Therefore, $f(n) \neq \Theta(f(n/2))$.

{\noindent {\bf 1 (Problem 2--4(h)).}} True.  We prove that for all functions
$f(n)$, $f(n) + o(f(n)) = O(f(n))$.  Let $g(n)$ by an function that is in
$o(f(n))$.  We need to show that $f(n) + g(n) = O(f(n))$.  Since $g(n) =
o(f(n))$, we have: for any constant $c > 0$, there exists a constant $n_0$
such that $0 \le g(n) < cf(n)$ for all $n \ge n_0$.  If we set $c = 1$, we
have: there exists a constant $n'_0$ such that $0
\le g(n) < f(n)$.

We now show that $f(n) + g(n) = O(f(n))$.  This is easy since $g(n) \le f(n)$
for all $n \ge n'_0$.  Therefore, $f(n) + g(n) \le f(n) + f(n) = 2f(n)$ for
all $n \ge n'_0$.


{\noindent {\bf 2 (Problem 4--1(d)).}} The solution to $T(n) = 7T(n/3) + n^2$
is $T(n) = \Theta(n^2)$. 
\begin{itemize}
\item
{\bf Master method:} Set $a = 7$, $b = 3$, and $f(n) = n^2$.  Since $\log_3 7
< 1.78 = 2 - .22$, $f(n) = n^2 = \Omega(n^{\log_3 7 + .22})$.  Thus, we need to
invoke Case~3 of the master method.  We need to check, however, if $7f(n/3)
\le c n^2$ for some constant $c < 1$.  We see that $7f(n/3) = 7(n/3)^2 =
7n^2/9 \le (7/9)n^2$.  Thus the check is satisfied.  It thus follows that
$T(n) = \Theta(n^2)$.

\item
{\bf Substitution:} We will first show that there exist positive constants $c$
and $n_0$ such that $0 \le T(n) \le c n^2$ for all $n
\ge n_0$.  Set $n_0$ equal to $1$.  So the boundary condition is that $T(1)
\le c$.  We will choose $c$ appropriately.  We now assume that the recurrence
holds for all values of $n$ less than $m$.  We will prove the claim for $n =
m$.
\begin{eqnarray*}
T(m) & =   & 7T(m/3) + m^2\\
     & \le & 7c (m/3)^2 + m^2\\
     & =   & (7c/9 + 1) m^2\\
     & \le & c m^2,
\end{eqnarray*}
if we select $c$ such that $7c/9 + 1 \le c$, which can be done by picking $c
\ge 9/2$.  This completes the upper bound.

For the lower bound, it trivially follows from the recurrence that $T(n) \ge
n^2$ for all $n$.  Therefore, $T(n) = \Omega(n^2)$.

\item
{\bf Iteration:} Again the lower bound is trivial.  For the upper bound we
proceed as follows:
\begin{eqnarray*}
T(n) & = & n^2 + 7T(n/3)\\
     & = & n^2 + 7((n/3)^2 + 7T(n/3^2))\\
     & = & n^2 + 7n^2/3^2 + 7^2T(n/3^2)\\
     & = & n^2 + 7n^2/3^2 + 7^2((n/3^2)^2 + 7T(n/3^3))\\
     & = & n^2 + 7n^2/3^2 + 7^2n^2/3^4 + 7^3T(n/3^3)\\
     & = & n^2(1 + 7/3^2 + 7^2/3^4) + 7^3T(n/3^3)\\
     & = & n^2(1 + 7/9 + 7^2/9^2 + \ldots 7^i/9^i) +
     7^{i+1}T(n/3^{i+1})\\
     & \le & n^2(1 + 7/9 + \ldots + 7^{\log_3 n - 1}/9^{\log_3 n - 1}) +
     7^{\log_3 n} T(2)\\
     & \le & n^2(1/(1 - 7/9)) + O(n^{\log_3 7})\\
     & \le & O(n^2) + O(n^2) \mbox{ (since $\log_3 7 < 2$)}\\
     & = & O(n^2).
\end{eqnarray*}
\end{itemize}

{\noindent {\bf 2 (Problem 4--1(e)).}} The solution to $T(n) = 7T(n/2) + n^2$
is $T(n) = \Theta(n^{\log_2 7})$.  We solve the recurrence by the master
method.  We set $a = 7$, $b = 2$, and $f(n) = n^2$.  Since $\log_2 7 > 2.8$,
we have $f(n) = n^2 = O(n^{\log_2 7 - .8})$.  Therefore, we invoke Case~1.  It
thus follows that $T(n) =
\Theta(n^{\log_2 7})$. 

{\noindent {\bf 2 (Problem 4--1(f)).}} The solution to $T(n) = 2T(n/4) +
\sqrt{n}$ is $T(n) = \sqrt{n} \log n$.  We use the master method here.
Set $a = 2$, $b = 4$, and $f(n) = \sqrt{n}$.  We then have $f(n) = \sqrt{n} =
\Theta(n^{\log_4 2})$.  Therefore, we invoke Case~2 and get $T(n) =
\Theta(\sqrt{n} \log n)$.

{\noindent {\bf 2 (Problem 4--1(h)).}} The solution to $T(n) = T(\sqrt{n}) +
1$ is $T(n) = \Theta(\lg \lg n)$.  We note that we cannot use the master
method here.  We therefore use the iteration method here.
\begin{eqnarray*}
T(n)
& = & 1 + T(n^{1/2})\\
& = & 1 + 1 + T(n^{1/4})\\
& = & i + T(n^{1/2^i})\\
& = & \Theta(\lg \lg n) + T(2) \mbox{ (since $n^{1/2^{\lg \lg n}} = n^{1/\lg
n} = 2^{(\lg n)/(\lg n)} = 2$)}\\
& = & \Theta(\lg \lg n).
\end{eqnarray*}

{\noindent {\bf 3.}} We are given two lists $A$ of $B$, each consisting of $n$
numbers.  We need to determine in $O(n \log n)$ time whether $A$ and $B$ have
a number in common.  There are several ways of doing this.  One algorithm is
the following:

\begin{tabbing}
1.  \= sort $A$ using mergesort;\\
2.\> \for\ \= each element $x$ in $B$\\
3.\>  \>search for $x$ in $A$ using binary search;\\
4.\>\>\myif\ the search is successful, then \ret\ TRUE;\\
5.\>\ret\ FALSE;
\end{tabbing}

{\bf Proof of Correctness:} If $A \cap B$ is empty, then the search for every
element $x$ in step $3$ would be unsuccessful.  Hence, the algorithm would
return FALSE.  If $A \cap B$ is not empty, then consider an element $x$ in $A
\cap B$.  Since $x \in B$, step~3 of the algorithm will search for $x$ in $A$
during some iteration of the for loop.  During that iteration, the search is
successful and the algorithm returns TRUE.

{\bf Analysis of the running-time:} Step~1 takes $O(n \log n)$ time.  Step~2
takes $O(n)$ time overall.  Step~3 takes $n \cdot O(\log n) = O(n \log n)$
time overall.  Step~4 takes $O(n)$ time overall.  Finally Step~5 takes $O(1)$
time.  Therefore, the running-time of the algorithm is $O(n \log n)$.

{\noindent {\bf 4(a).}} We show by induction on $n \ge 1$ that:
\[
A^n = \left( 
\begin{array}{cc}
F_{n+1} & F_n\\
F_n & F_{n-1}
\end{array}
\right).
\]
The induction base ($n = 1$) follows directly from the definition of $A$ and
the fact that $F_0 = 0$ and $F_1 = F_2 = 1$.

We now establish the induction step for $n = m \ge 2$ assuming that the claim holds
for all $n < m$.  We write $A^m$ as $A^{m-1} A$ and obtain:
\[
A^m  =  \left(
\begin{array}{cc}
F_m & F_{m-1}\\
F_{m-1} & F_{m-2}
\end{array}
\right)
\cdot
\left(
\begin{array}{cc}
1 & 1\\
1 & 0
\end{array}
\right)
= \left(
\begin{array}{cc}
F_m + F_{m-1} & F_m\\
F_{m-1} + F_{m-2} & F_{m-1}\\
\end{array}
\right)
= \left(
\begin{array}{cc}
F_{m+1} & F_m\\
F_m & F_{m-1}
\end{array}
\right).
\]

{\noindent {\bf 4(b).}} It follows from Problem~4(a) that in order to compute
$F_n$, it is enough to compute $A^{n-1}$.  We now give an $O(\log n)$ time
algorithm for computing $A^n$.

\begin{tabbing}
\POWER($A$, $n$)\\
1.  \= \myif\ $n = 1$, then \ret\ $A$;\\
2.\> \myif\ $n$ is odd, then \ret\ $A \cdot [\mbox{\POWER}(A, (n-1)/2)]^2$;\\
3.\> \myelse\ \ret\ $[\mbox{\POWER}(A, n/2)]^2$;
\end{tabbing}

{\bf Proof of Correctness:} The proof is by induction on $n$.  For the base
case ($n = 1$), we note that \POWER($A$, 1) returns $A$.  We now prove the
induction step.  We assume that \POWER($A$, i) returns $A^i$ for all $i < m$.
We need to show that \POWER($A$, $m$) returns $A^m$.  We consider two cases.
First, if $m$ is odd, then \POWER($A$, $m$) returns $A \cdot \POWER(A,
(m-1)/2)^2$, which, by the induction hypothesis, equals $A \cdot A^{m-1} =
A^m$.  Second, if $m$ is even, then \POWER($A$, $m$) returns
$(\POWER(A,m/2))^2$, which, by the induction hypothesis, equals $(A^{m/2})^2 =
A^m$.  This completes the proof of correctness.

{\bf Analysis of the running-time:} Step~1 takes constant time.  Aside from
the recursive calls, Steps~2 and~3 involve 3 and 2 matrix multiplications,
respectively.  Since all of the matrices involved are $2 \times 2$ matrices,
each of the multiplications takes $O(1)$ time.  Each of the recursive calls
takes $T(\lfloor n/2 \rfloor)$ time.  We thus have the following recurrence
for the running time $T(n)$.
\begin{eqnarray*}
T(n) & \le & O(1) + T(n/2)\\
     & \le & O(1) + O(1) + T(n/2^2)\\
     & \le & O(i) + T(n/2^i)\\
     & = & O(\lg n) \mbox{ (since $n/2^{\lg n} = 1$)}.
\end{eqnarray*}


{\noindent {\bf 5(a).}} Let $X_i$ denote the random variable that equals $1$
if bin $i$ is empty, and $0$ otherwise.  Let $X$ denote the random variable
representing the number of empty bins.  We have $X = \sum_{i = 1}^{n} X_i$.
The probability that bin $i$ is empty is $(1 - 1/n)^n \le 1/e$.  Therefore,
$E[X_i] \le 1/e$.  Since $E[X] = \sum_{i = 1}^n E[X_i]$, we have $E[X] \le
n/e$. 

{\noindent {\bf 5(b).}} Let $k$ equal $4\lg n/\lg \lg n$.  Let $E$ denote the
event that some bin receives at least $k$ balls.  Let $E_i$ denote the event
that bin $i$ receives at least $k$ balls.  We first show that for all $i$,
$\Pr[E_i] \le {n \choose k} 1/n^k$.  For convenience, we use $m$ to denote ${n
\choose k}$.  Let $S_1$, $S_2$, \ldots, $S_m$ denote the $m$ different ways of
selecting $k$ balls out of $n$.  (Thus, each $S_i$ is a set of $k$ balls.)
Let $E_{ij}$ denote the event that every ball in $S_j$ falls in bin $i$.  It
is easy to see that $\Pr[E_{ij}]$ equals $1/n^k$.

We claim that $E_i = \cup_{i = 1}^{m} E_{ij}$.  To see this, first
observe that if the event $E_i$ occurs, then there exist $k$ balls that fall
in bin $i$ and these balls must form one of the $m$ sets among $S_1$, $S_2$, \ldots, $S_{m}$.  Let us say
the set is $S_j$.  This implies that the event $E_{ij}$ occurs.  Therefore,
$E_i \subseteq \cup_{i = 1}^{m} E_{ij}$.  Similarly, if $E_{ij}$
occurs for some $j$, then this implies that every ball in $S_j$ lands in bin
$i$.  Hence at least $k$ balls land in bin $i$.  Therefore, $E_i \supseteq
\cup_{i = 1}^{m} E_{ij}$.  We thus have $E_i = \cup_{i = 1}^{m} E_{ij}$.  By Boole's inequality, we have:
\begin{eqnarray}
\Pr[E_i] \le \sum_{j = 1}^{m} \Pr[E_{ij}] = {n \choose k}
(1/n)^k \label{eqn:E_i}
\end{eqnarray}
(It is {\em very important}\/ to note that $\Pr[E_i] \neq \sum_{j = 1}^{m}
\Pr[E_{ij}]$.  This is because the $E_{ij}$'s, $j$ running from $1$ to $m$,
are not mutually exclusive.)

We now apply the inequality ${n \choose k} \le (en/k)^k$ and plug the value of
$k$ into Equation~\ref{eqn:E_i} to obtain:
\begin{eqnarray*}
\Pr[E_i] & \le & \left(\frac{en}{nk}\right)^k\\
         & \le & \left(\frac{e}{k}\right)^k\\
         & \le & \left(\frac{e\lg \lg n}{4 \lg n}\right)^{4\lg n/\lg \lg n}\\
         & \le & \left(\frac{\lg \lg n}{\lg n}\right)^{4\lg n/\lg \lg n} \mbox{ (since $e
         > 4$)}\\
         & = & \left(\frac{1}{2^{\lg \lg n - \lg \lg \lg n}}\right)^{4\lg n/\lg \lg
         n}\\
         & = & \left(\frac{1}{2}\right)^{(4\lg n)(1 - \lg \lg \lg n/\lg \lg n)}\\
         & \le & \left(\frac{1}{2}\right)^{(4\lg n)(1 - 1/2)} \mbox{ (since $\lg \lg n \ge
         2 \lg \lg \lg n$ for all $n \ge 16$)}\\
         & = & \left(\frac{1}{2}\right)^{2\lg n}\\
         & = & \frac{1}{n^2}.
\end{eqnarray*}
Finally, since $E$ equals $\cup_{i = 1}^n E_i$, we apply Boole's inequality
again to obtain that $\Pr[E] \le n/n^2 = 1/n$.  This completes the proof of
the desired claim.

{\noindent {\bf 6 (Problem 8--3(a)).}} To prove that \SS($A, i, j$) sorts
correctly, we use induction on $\ell = j - i + 1$.  (That is, $\ell$ is the
number of elements in $A[i.. j]$.)  For the induction basis, we consider
two cases: $\ell = 1$ or $\ell = 2$, i.e., $i = j$ or $i = j -1$.  For each of
these cases, in Steps~1 and~2, $A[i]$ and $A[j]$ are exchanged if $A[i] >
A[j]$.  Also, in both cases the condition in Step~3 holds.  Therefore, \SS($A,
i, j$) returns after having sorted $A$.

For the induction hypothesis, we assume that \SS\ sorts correctly for all
arrays of length less than $m$, where $m > 2$.  We now show that \SS\ sorts
correctly for all inputs of length $m$.  Since $m > 2$, the condition in
Step~3 is not true; hence \SS\ does not return in Step~4.  Moreover, for the
discussion that follows, it does not matter whether the exchange of $A[i]$ and
$A[j]$ took place in Step~2.  So we now consider Steps~5 through~8.  The
variable $k$ is set to $\lfloor(j - i + 1)/3\rfloor$ in Step~5.  Since $j - i
+ 1 \ge 3$, $k \ge 1$; therefore, $j - i - k + 1 = m - k < m$.  Therefore, the
length of the array $A[i.. j- k]$ on which \SS\ is called in Step~6 is less
than $m$.  By the induction hypothesis, it follows that $A[i.. j - k]$ is in
sorted order after Step~6.  Hence, $A$ has the following property: (P1) for
all $x$ in $[i.. i + k - 1]$ and $y$ in $[i+ k.. j- k]$, $A[x] \le A[y]$.  In
particular, we see that there are at least $k$ elements in $A[i+k.. j]$ that
are greater than or equal to every element in $A[i.. i+k-1]$.  Next, \SS\
sorts $A[i + k, .., j]$.  Again, the length of the array is less than $m$.  So
we invoke the induction hypothesis and claim that after Step~7, $A[i + k.. j]$
is sorted. Since $A[i+k.. j]$ is sorted, $A$ has the following property:
(P2) $A[j-k+1.. j]$ is sorted correctly, and (P3) for all $x$ in $[i + k.. j -
k]$ and $y$ in $[j - k + 1.. j]$, $A[x] \le A[y]$.

Since the elements in indices $[i.. i+k-1]$ do not move, the following
property (that follows from~(P1)) still holds: (P4) there are at least $k$
elements in $A_7[i+k.. j]$ that are greater than or equal to every element in
$A[i.. i+k-1]$.  Therefore, combining with property~(P3) above, we have: (P5)
for all $x$ in $[i.. j - k]$ and $y$ in $[j - k + 1.. j]$, $A[x] \le A[y]$.
Thus, after step~6, properties~(P2) and~(P5) hold.

Finally, we apply \SS\ on $A[i.. j -k]$.  Again the length of the array, $j -
k - i + 1$ is less than $m$.  So applying the induction hypothesis, we obtain
that $A[i.. j - k]$ is sorted correctly.  Moreover, since the indices
$[j-k+1.. j]$ are unaffected, properties~(P2) and~(P5) still hold.  We thus
obtain that the entire array $A[i.. j]$ is sorted correctly.

{\noindent {\bf 6 (Problem 8--3(b))}} Let $T(n)$ be the running time of \SS\
on an array of length $n$.  Steps~1 through~5 take $\Theta(1)$ time.  Steps~6
through~8 take $T(n - k)$ time.  Since $k = \lfloor n/3 \rfloor$, $2n/3 \le n
- k \le 2n/3 + 1$.  We show by the substitution method that $T(n) =
\Theta(n^{\log_{3/2} 3})$.  We will show that there exist constants $c$,
$c_1$, $c_2$, and $n_0$ such that $cn^{\log_{3/2} 3} \le T(n) \le c_1
n^{\log_{3/2} 3} - c_2 n^2$ for all $n \ge n_0$.  Since $\log_{3/2} 3 > 2$,
this yields the desired tight bound.  We first establish the induction step
for the upper bound.  For $n \ge 3$, we have:
\begin{eqnarray*}
T(n) & \le & 3(c_1(2n/3 + 1)^{\log_{3/2} 3} - c_2(2n/3 + 1)^2) + O(1)\\
     & \le & 3c_1((2n/3)^{\log_{3/2} 3} + c_3 n^2) - 3c_2(2n/3 + 1)^2 + O(1)\\
     & \le & c_1n^{\log_{3/2} 3} + 3c_1c_3 n^2 - 4c_2 n^2/3 + O(n)\\
     & \le & c_1n^{\log_{3/2} 3} - c_2 n^2 - (c_2n^2/3 - 3c_1c_3n^2 - O(n))\\
     & \le & c_1n^{\log_{3/2} 3} - c_2 n^2.
\end{eqnarray*}
(In the second step, $c_3$ is a constant that is obtained when we consider the
non-leading terms in the binomial expansion of $(2n/3 + 1)^{\log_{3/2} 3}$.
The last step holds since we can choose $c_2/c_1$ sufficiently large such that
$(c_2/c_1) \ge 3c_3 + O(1)$ .)  For the lower bound, we have:
\begin{eqnarray*}
T(n) & \ge & 3c(2n/3 + 1)^{\log_{3/2} 3}\\
     & = &  cn^{\log_{3/2} 3}.
\end{eqnarray*}
Finally, we note that we can select $n_0$ and $c_1$ sufficiently large and $c$
sufficiently small such that that $cn^{\log_{3/2} 3} \le T(n_0) \le c_1
n^{\log_{3/2} 3} - c_2 n^2$.

{\noindent {\bf 6 (Problem 8--3(c))}.} Since $T(n) = \Theta(n^{\log_{3/2} 3}) =
\omega(n^2)$, \SS\ is worse than each of insertion sort, merge sort, heapsort,
and quicksort.  

{\noindent {\bf 7(a).}} The calculation of $m$ and $M$ can be done in
$\Theta(n)$ time.  Finding a random number is assumed to take constant time.
Finally, we have seen in class that partitioning takes $\Theta(n)$ time.
Therefore, the running time of {\sc New-Partition} is $\Theta(n)$.

{\noindent {\bf 7(b).}} Let $n - 1$ numbers of the array be $m + i$ for $0 \le
i \le n - 2$.  Let the $n$th number be $M$.  The probability that $A_\ell$ is
exactly $n - 1$ equals the probability that the random number falls in the
interval $[m+n-2..M-1]$.  Hence the probability equals $(M -m - n +1)/(M - m +
1) = 1 - n/(M - m + 1)$.  For any $\eps > 0$, we can choose $M - m$ to be
sufficiently large such that $n/(M - m + 1) \le \eps$.  Hence the probability
that $A_{\ell}$ is $n-1$ can be made arbitrarily close to $1$.

{\noindent {\bf 7(c).}} If we use {\sc Randomized-Partition}, then the
expected running time of {\sc Randomized-Quicksort} is independent of the
input array $A$.  If we use {\sc New-Partition}, however, then the expected
running time can be made to be $\Omega(n^2)$ by selecting $A$ maliciously.

In part~(b), we described an input $A$ that results in a highly unevenly
balanced partitioning with ``high probability'' for one pariticular iteration.
This is in stark contrast to what is true for the procedure {\sc
Randomized-Partition} that we studied in class.  For all inputs $A$, {\sc
Randomized-Partition} has the property that all of the splits of $A$ are {\em
equally likely}.  (For the procedure given in text, all of the splits have
``approximately'' the same probability; that suffices to prove the $O(n \log
n)$ upper bound for {\sc Randomized-Quicksort}.)

Thus, it appears that {\sc New-Partition} is not a good partitioning procedure
for {\sc Randomized-Quicksort}.  We now formalize this intuition.  We present
an input $A$ such that {\sc New-Partition} results in an uneven
partitioning with high probability in every iteration.  Let $A$ consist of the
numbers $1, 2, \ldots, 2^i, 2^{n-1}$.  Let us assume that the partitioning
results in two parts, one consisting of all elements less than or equal to
the pivot $r$, and the other consisting of all elements more than $r$.  The,
it can be seen that when {\sc Randomized-Quicksort} is called on any subarray
of length $m$, the probabilities of the different splits will be the
following.  With probability $1/2^m$, the split is $m$ and $0$ (this is the
case where the random number is $M$).  With probability $1/2$, the split is
$m-1$ and $1$.  With probability $1/2^2$, $m-2$ and $2$.  And, in general,
with probability $1/2^i$, the split is $m-i$ and $i$, where $1 \le i < m$.
(Note that for this choice of $A$, the probability that the low side of the
partition is $m - 1$ is not close to 1; it is $1/2$, but such a bound is
sufficient for our purposes.)

We obtain the following recurrence for the expected running time of {\sc
Randomized-Quicksort} on the array $A$:
\begin{eqnarray*}
T(n) & = & \frac{1}{2^n} T(n) + \sum_{i = 1}^{n-1} \frac{1}{2^i}\left(T(n - i)
+ T(i)\right) + \Theta(n).
\end{eqnarray*}
We now show that $T(n) = \Omega(n^2)$.  The proof is by the substitution
method.  We establish the induction step for the claim $T(n) \ge cn^2$, where
$c$ will be chosen appropriately.
\begin{eqnarray*}
T(n) & \ge & \sum_{i = 1}^{n-1} \frac{1}{2^i}\left(c(n-i)^2 + ci^2\right) +
\Theta(n)\\
     & \ge & \sum_{i = 1}^{n-1} \frac{c}{2^i}\left(n^2 - 2ni + 2i^2\right) +
\Theta(n)\\
     & \ge & cn^2 \sum_{i = 1}^{n-1} \frac{1}{2^i} - 2cn \sum_{i = 1}^{n-1}\frac{i}{2^i} + \Theta(n)\\
     & \ge & cn^2(1 - 1/2^n) - 4cn + \Theta(n) \mbox{ (since
$\sum_{i=1}^{n-1}1/2^i = 1 - 1/2^n$ and $\sum_{i = 1}^{\infty} i/2^i \le 2$)}\\
     & \ge & cn^2 + (\Theta(n) - 4cn - cn^2/2^n)\\
     & \ge & cn^2.
\end{eqnarray*}
(For the last step, we choose $c$ to be sufficiently small such that the
constant in the term $\Theta(n)$ dominates $4c$.)
We thus have $T(n) = \Omega(n^2)$.  It thus follows that {\sc New-Partition}
is a bad replacement for {\sc Randomized-Partition}.
\end{document}