\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\newcommand{\k}{\mbox{\it key}}
\newcommand{\SS}{\mbox{{\sc Stooge-Sort}}}

\head{3390}{Analysis of Algorithms}{Spring 1999}{28 April 1999}{11}

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

\bigskip

{\bf 1. (10 points)} Let 
\[
p(n) = \sum_{i = 0}^{d} a_i n^i
\]
be a degree-$d$ polynomial in $n$, where $a_0$ through $a_d$ are arbitrary
real constants and $a_d > 0$.  Using the definition of $\Theta$-notation,
prove that $p(n) = \Theta(n^d)$.

{\bf Answer:} We first provide an upper bound on $p(n)$.  Let $M$ equal
$\max\{|a_i| : 0 \le i \le d\}$.  That is, $M$ is the maximum among all
$|a_i|$.  
\begin{eqnarray*}
p(n) 
& = & \sum_{i = 0}^d a_i n^i \\
& \le & \sum_{i = 0}^d M n^i \\
& \le & (d+1)Mn^d,
\end{eqnarray*}
for all $n \ge 1$.  Since $(d+1)M$ is a constant, we obtain that $p(n) = O(n^d)$.
(The part $p(n) \ge 0$ is established below for $n$ sufficiently large.)

We now provide a lower bound on $p(n)$.  It is tempting to write that $p(n)
\ge a_d n^d$, but the claim is not true because the $a_i$'s (apart from $a_d$)
could be negative.  
\begin{eqnarray*}
p(n)
& = & \sum_{i = 0}^d a_i n^i \\
& = & a_d n^d + \sum_{i = 0}^{d  - 1} a_i n^i\\
& \ge & a_d n^d - \sum_{i = 0}^{d-1} M n^i\\
& \ge & a_d n^d - dM n^{d-1}\\
& \ge & a_d n^d/2,
\end{eqnarray*}
for $n \ge 2dM/a_d$.  Since $a_d/2$ and $2dM/a_d$ are constants, we obtain
that $p(n) = \Omega(n^d)$.  Note that the above lower bound also implies that
$p(n) \ge 0$ for $n \ge 2dM/a_d$, a claim that is needed for the $O$-bound.
  

{\bf 2. (10 points)} Arrange the following functions in order from the slowest
growing function to the fastest growing function.  Briefly justify your
answer.  ({\em Hint:} It may help to express each function as a power of $2$
and then compare.)

\[ 
(\lg n)^{\lg n} \hs (\frac{3}{2})^{2n} \hs n^{100} \hs 2^{\sqrt{\lg n}}
\]

{\bf Answer:} The order from slowest growing to the fastest growing function
is: $2^{\sqrt{\lg n}}$, $n^{100}$, $(\lg n)^{\lg n}$, $(\frac{3}{2})^{2n}$.
We prove this using three steps: (i) $2^{\sqrt{\lg n}} = o(n^{100})$, (ii)
$n^{100} = o((\lg n)^{\lg n})$, and (iii) $n^{100} = o((\frac{3}{2})^{2n})$.
\begin{itemize}
\item[(i)] We use the connection between asymptotic notation and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{2^{\sqrt{\lg n}}}{n^{100}} & = & 
\lim_{n \rightarrow \infty} \frac{2^{\sqrt{\lg n}}}{2^{100\lg n }}\\
& = & \lim_{n \rightarrow \infty} \frac{1}{2^{100\lg n - \sqrt{\lg n}}}\\
& = & 0,
\end{eqnarray*}
since $100 \lg n - \sqrt{\lg n}$ tends to $\infty$ as $n$ tends to $\infty$.
\item[(ii)] We again use the connection between asymptotic notation and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{n^{100}}{(\lg n)^{\lg n}} & = & 
\lim_{n \rightarrow \infty} \frac{2^{100 \lg n}}{2^{\lg n \lg \lg n}}\\
& = & \lim_{n \rightarrow \infty} \frac{1}{2^{\lg n (\lg \lg n - 100)}}\\
& = & 0,
\end{eqnarray*}
since $\lg \lg n - 100$ tends to $\infty$ as $n$ tends to $\infty$.

\item[(iii)] We again use the connection between asymptotic notation and
limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{(\lg n)^{\lg n}}{(\frac{3}{2})^{2n}} & \le & 
\lim_{n \rightarrow \infty} \frac{(\lg n)^{\lg n}}{(2^{n}}\\
& = & \lim_{n \rightarrow \infty} \frac{2^{\lg n \lg \lg n}}{2^{n}}\\
& \le & \lim_{n \rightarrow \infty} \frac{1}{2^{\lg n (n - \lg n \lg \lg n)}}\\
& = & 0,
\end{eqnarray*}
since $n - \lg n \lg \lg n$ tends to $\infty$ as $n$ tends to $\infty$.
\end{itemize}

{\bf 3. (2 $\times$ 5 = 10 points)} Let $f(n)$, $g(n)$, and $h(n)$ be
asymptotically positive and monotonically increasing functions.  Prove
or disprove each of the following conjectures.
\begin{itemize}
\item[{\bf (a)}]
$f(n) + g(n) = \Theta(\max\{f(n), g(n)\})$.

{\bf Answer:} True.  We first note that since the two functions are
asymptotically positive, if $n$ is sufficiently large, then $f(n) + g(n) \ge
\max\{f(n), g(n)\}$.  Therefore, $f(n) + g(n) = \Omega(\max\{f(n), g(n)\})$.
For the other part, we note that $f(n) + g(n) \le 2 \max\{f(n), g(n)\}$ for
all $n$, thus implying that $f(n) + g(n) = O(\max\{f(n), g(n)\})$.

\item[{\bf (b)}]
$f(n^2) = O((f(n))^2)$.

{\bf Answer:} False.  Let $f(n) = 2^n$.  Then $f(n^2) = 2^{n^2}$ and $(f(n))^2
= (2^n)^2 = 2^{2n}$.  We now show using limits that $f(n^2)$ is
$\omega((f(n))^2)$.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{2^{n^2}}{2^{2n}} & = & 
\lim_{n \rightarrow \infty} 2^{n^2- 2n}\\
& = & \infty,
\end{eqnarray*}
since $n^2 - 2n$ tends to $\infty$ as $n$ tends to $\infty$.
\end{itemize}

{\bf 4. (3 $\times$ 5 = 15 points)} Solve the following recurrences.
Assume that $T(n)$ is constant for $n \le 2$.  
\begin{itemize}
\item[{\bf (a)}]
$T(n) = 2T(n/4) + \sqrt{n}$.

{\bf Answer:} We use the master method.  We have $a = 2$, $b = 4$, and $f(n) =
\sqrt{n}$.  Therefore, $n^{\log_b a} = \sqrt{n}$.  Thus, we invoke Case~2 and
obtain that $T(n) = \Theta(\sqrt{n} \lg n)$.

\item[{\bf (b)}]
$T(n) = T(\sqrt{n}) + 1$.

{\bf Answer:} The solution to this recurrence is 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*}

\item[{\bf (c)}] $T(n) = T(\alpha n) + T((1 - \alpha)n) + n$, where $\alpha$
is a real constant in the range $0 < \alpha < 1$.  ({\em Hint:} Use a
recursion tree.)

{\bf Answer:} We use a recursion tree.  The contribution of the first level of
the tree is $n$.  The contribution of the second level is $\alpha n + (1 -
\alpha)n = n$.  The contribution of the third level is $\alpha^2 n + 2\alpha(1
- \alpha) n + (1 - \alpha)^2 n = n$.  We can thus show that the contribution
of $i$th level is $n$, as long as $i \le \min\{ \log_{1/\alpha} n,
\log_{1/(1-\alpha)} n\}$.  Note that $\log_{1/\alpha} n$ is the distance of
the root of the recursion tree to the leftmost leaf and $\log_{1/(1 -\alpha)}
n$ is the distance of the root of the recursion tree to the rightmost leaf.
Therefore, the total contribution is at most $n \max\{ \log_{1/\alpha} n,
\log_{1/(1-\alpha)} n\}$, thus indicating that $T(n) = O(n \lg n)$, since
$\alpha$ is a constant.  Similarly, $T(n)$ at least $n \min\{ \log_{1/\alpha}
n, \log_{1/(1-\alpha)} n\}$, thus implying that $T(n) = \Theta(n \lg n)$,
since $\alpha$ is a constant.
\end{itemize}

{\bf 5. (15 points)} Problem~4--7, page 75.

{\bf Answer of part (a):} We will prove the desired claim under the assumption
that the number of good and bad chips are the same.  If the number of bad
chips is greater than the number of good chips, then this makes the task of
finding a good chip only harder.  

Now let $G$ be the set of good chips and $B$ be the set of bad chips.  Suppose
each bad chip reports a good chip as bad and a bad chip as good.  Then we have
the following property: (i) all the pairwise tests within $G$ report
good-good, (ii) all pairwise tests within $B$ report good-good, and (iii) all
pairwise tests involving one chip in $G$ and the other in $B$ report bad-bad.
This implies that after doing all the pairwise tests, the professor will not
be able to distinguish the set $G$ from $B$ since their behavior is exactly
the same, and so is their number.  Thus, even though the professor may be able
to identify that all of the chips in $G$ are either all good or all bad and
the chips in $B$ are all good or all bad, he or she will not be able to
identify a single good chip.

{\bf Answer of part (b):} Let $S$ be the given set of $n$ chips.  Let $g$ be
the number of good chips and $b$ be the number of bad chips.  We group the
given set $S$ chips into pairs.  If $n$ is odd, then there may be an unpaired
chip.  Thus, we have $\lfloor n/2 \rfloor$ pairs of two chips each.  We load
each pair into the jig and perform the pairwise test.

We will construct a set $S'$ of at most $\lceil n/2 \rceil$ chips such that at
least half of them are good.  We go through the results of the pairwise tests.
If the test result is good-bad, then we throw out the chip that tested bad and
add to $S'$ the chip that tested good.  If the test result is good-good, then
we add to $S'$ any one of the chips and throw the other.  If the test result
is bad-bad, then we throw out both the chips.  Since, at most chip from each
pair is included in $S'$, it is clear that the number of chips in $S'$ is at
most $\lfloor n/2 \rfloor$.  Finally, if the number of chips thus included is
an even number, then we add the unpaired chip to $S'$.  We thus have $|S'| \le
\lceil n/2\rceil$.

Let $gg$, $bb$, and $gb$ be the number of pairwise tests involving two good
chips, two bad chips, and one good chip and a bad chip, respectively.  (Note
that the terms ``good'' and ``bad'' in the preceding sentence refer to the
actual quality of the chip, not the outcome of the test.)  Let $x$ and $y$
denote the number of good chips and bad chips, respectively, that were picked
during the pairwise tests.  When two good chips pair together, the output of
the test is $GG$; therefore at least one of the chips is included in $S'$.  If
a good chip and a bad chip pair together, then the result is either a $GB$ or
a $BB$.  In the former case, only the good chip is picked.  In the latter
case, both chips are discarded.  Finally, when two bad chips are paired
together, at most one of the chips is selected.  Thus, we have 
$x \ge gg$ and $y \le bb$.

Since the number of good chips is at least $n/2$, we have $gg > bb$ if $n$ is
even or if $n$ is odd and the unpaired chip is bad.  If $n$ is odd and the
unpaired chip is good, then $gg \ge bb$.  We thus have $x \ge y$.  We still
have to account for the unpaired chip, which arises only if $n$ is odd.
Recall that we pick the unpaired chip only if the number of chips selected
after the pairwise tests is even.  If $x + y$ is odd, then since $x \ge y$, it
follows that $x > y$ and we are done in this case.  If $x + y$ is even, then
we have two cases: either $x = y$ or $x \ge y + 2$.  The former case can only
arise if $x = gg = bb = y$.  And $gg = bb$ can only happen if the unpaired
chip is good, which makes the number of good chips in $S'$ one more than the
number of bad chips.  Finally, if $x \ge y + 2$, then adding another chip
still leaves the good chips with a clear majority.  This completes the proof.

{\bf Answer of part (c):} We first identify a good chip by using the procedure
of part~(b) recursively.  The recursion for this procedure is given by
\[
T(n) = T(\lceil n/2 \rceil) + \lfloor n/2 \rfloor.
\]
Ignoring the ceiling, we obtain the recurrence $T(n) \le T(n/2) + n/2$,
which can be shown to be $O(n)$ using case~3 of the master method.  We can
also give a precise proof usin the substitution method, where we do not ignore
the ceiling.

Once we have identified a good chip, we test the chip with each of the other
$n-1$ chips and identify their quality.  This procedure takes $n - 1 =
\Theta(n)$ tests.  Thus the total number of pairwise tests is $\Theta(n)$.

{\bf 6. (6 + 6 + 3 = 15 points)} Problem~8--3, page 169.  For part~(c), use
the fact that worst-case running time of heapsort is $\Theta(n \log n)$.

{\bf Answer of part (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.

{\bf Answer of part (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$.

{\bf Answer of part (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.

{\bf 7. (8 + 9 + 8 = 25 points)} The worst-case running time of both insertion
sort and quicksort is $\Theta(n^2)$.  Quicksort is considered an efficient
sorting algorithm because the average-case running time of quicksort (assuming
that all orderings are equally likely) is $\Theta(n \lg n)$.  In this
exercise, we take a closer look at insertion sort.  (For the pseudocode of
insertion sort, you may refer to your class notes or to Section 1.2 of the
textbook.)

Let $A[1..n]$ be an array of $n$ distinct numbers.  If $i < j$ and $A[i] >
A[j]$, then we say that the pair $(i,j)$ is an {\em inversion}\/ of $A$.

\begin{enumerate}
\item[{\bf (a)}] 
If $T(A)$ is the running time of insertion sort on input $A$ and $I(A)$ is the
number of inversions in $A$, then prove that $T(A)$ is $\Theta(I(A) + n)$.

{\bf Answer:} Consider what happens in the $j$th for loop of insertion sort.
(See pseudocode on page 8 of text.)  At the start of this for loop, all of the
elements in $A[1..j-1]$ have been sorted.  In the for loop, we first set $\k$
to $A[j]$ (line 2) and then compare it with elements $A[j-1]$, $A[j-2]$,
\ldots, (the while-loop in lines 5 through 7) until an element smaller than or
equal to $\k$ is found.  Thus the total number of executions of the
while-statement is exactly equal to 1 more than the number of elements that
are in the first $(j - 1)$ positions and are greater than $A[j]$.  But the
elements that are in the first $(j - 1)$ positions and are greater than $A[j]$
exactly correspond to the number of inversions of the form $(\cdot, j)$ in
$A$.  Thus, if we add over all of the for loops, we get that the total number
of while loop executions is $I(A) + (n - 1)$.  Since there are only a constant
number of operations in each while loop, the running time of insertion sort is
$\Theta(I(A) + n)$.


\item[{\bf (b)}]
Show that if $A$ is a random permutation chosen uniformly at random
from the set of all $n!$ permutations, then the expected number of
inversions is $\Theta(n^2)$.  Using part~(a), derive a tight bound on the
expected running time of insertion sort on a random permutation.

{\bf Answer:} Consider a pair $(i, j)$.  If we select a random permutation,
what is the probability that this pair is an inversion?  Since both $A[i] >
A[j]$ and $A[j] > A[i]$ are equally likely, this probability is $1/2$.
Therefore, any pair $(i, j)$ contributes $1$ to the total number of inversions
with probability $1/2$, and $0$ with probability $1/2$.  Therefore, the
expected contribution of each pair is $1/2$.

As we have seen, there are a total of $n(n-1)/2$ possible pairs $(i, j)$.  Since
the expected contribution  of each pair is $1/2$, the expected total number of
inversions $I(A)$ is $n(n-1)/4$.  Therefore, by part~(b), the expected running
time equals $\Theta(n(n-1)/4 + n) = \Theta(n^2)$. 

\item[{\bf (c)}]
Using part~(a), solve Exercise 8.4--4, page 167.

{\bf Answer:} We need to determine the cost of the modified quicksort
procedure and the insertion sort call.  Using an informal argument, we first
place a bound on the running time of modified quicksort.  The expected levels
of recursion in the usual randomized quicksort is $O(\lg n)$.  Note that each
level contributes $O(n)$, thus leading to an expected running time of $O(n \lg
n)$.  If we stop the recursion when the size of the subarray is at most $k$,
then the expected number of levels of recursion becomes $O(\lg (n/k))$.  (This
is what is needed to be proven formally.)  Therefore, the contribution of
quicksort is $O(n\lg (n/k))$

We will now determine the cost of the insertion sort procedure using part (a).
The key point is to note that after the quicksort procedure completes, the
state of the array is as follows: it can be partitioned into {\em sorted}\/
groups, each of size at most $k$ and at least $k/2$.  (The lower bound of
$k/2$ occurs since we are not recursing on any subarray of size at most $k$.)
Thus the number of groups is at most $2n/k$, with each group having at most
$k^2/2$ inversions.  Note that there are no inversions across groups.
Therefore, the total number of inversions is at most $nk$, which is $O(nk)$.
This yields the desired bound on the running time.

The bound on the expected running time is $O(nk + n \lg (n/k))$.  Note that
the first term in the expression increases with $k$ and the second decreases
with $k$.  The sum of the two terms will be dominated by the larger term.  So
the expression is minimized when we choose $k$ such that the two terms are
``equal'', asymptotically.  So we set $nk = \Theta(n \lg(n/k))$, which yields
$k = \Theta(\lg (n/k))$.  One can see that if we set $k = \Theta(\lg n)$, then
the right hand side equals $\Theta(\lg (n/\lg n)) = \Theta(\lg n - \lg\lg n) =
\Theta(\lg n)$.  

In practice, one should again choose $k$ so as to balance the quicksort
portion and the insertion sort portion.  But attention must be given to the
constants hidden in the notation above.

Let's get back to the analysis of the modified quicksort.  The only
modification done here is to set the base case at $n = k$ rather than $n =
1$.  So this yields the following recurrence (compare with the recurrence in
Section~8.4 of the text):
\begin{eqnarray*}
T(n) \le \frac{2}{n}\sum_{i = k+1}^{n-1} T(i) + \Theta(n).
\end{eqnarray*}
Note that the only difference with the recurrence in the text (that we also
covered in class) is that $i$ goes from $k + 1$ to $n-1$ rather than from $0$
to $n - 1$.  The reason is that the modified quicksort procedure does not
recurse for any input size that is at most $k$.  We can now solve the above
recurrence using the substitution method in a manner similar to what we did
for randomized quicksort and show that $T(n) = O(n \lg (n/k))$.  

The main challenge while solving the recurrence arises in the induction step
of the substitution method.  This is in placing a bound on the summation
$\sum_{i = k+1}^{n-1} i \lg i$.  Recall that in class we placed a bound on the
summation $\sum_{i = 1}^{n-1} i \lg i$.  One can show that this is upper
bounded by $(n^2\lg(n/k))/2 - n^2/8 + n/4 + k^2/2$.  Notice the $(n/k)$
instead of $n$ in the $\lg$-term and extra $k^2/2$.  If we use this bound in
the inductive step, then we can complete the proof.  The details of the proof,
which provide a useful exercise, are left to the reader.


\junk{
During the induction
step, we get that
\begin{eqnarray*}
T(n) & \le & \frac{2}{n}\sum_{i = k+1}^{n-1} i\lg(i/k) + \Theta(n)\\
& \le & \frac{2}{n}\sum_{i = k+1}^{n-1} (i\lg i - i \lg k) + \Theta(n)\\
& \le & \frac{2}{n}\sum_{i = k+1}^{n-1} i \lg i - (\lg k) \sum_{i = k +
1}^{n-1} i + \Theta(n)\\
& \le & \frac{2}{n}\sum_{i = k+1}^{n-1} i \lg i - (\lg k)(n(n-1)/2 - k(k+1)/2)
+ \Theta(n)\\
& \le & \frac{2}{n}\sum_{i = k + 1}^{n-1} i \lg i - (n-1)\lg k +
\frac{k(k+1)(\lg  k)}{2n} + \Theta(n)\\
& \le & 

Recall that the main challenge there was to show that $\sum_{i = 0}^{n-1} i
\lg i \le (n^2 \lg n)/2 - n/8$.  Here, we can show that }
\end{enumerate}
\end{document}



