\documentclass{article}

\usepackage{fullpage}
\usepackage{latexsym}

\usepackage{amsmath}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                         %%%
%%%  Initializations & Definitions                                          %%%
%%%                                                                         %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\input{macros}

\newcommand{\bfif}{{\bf if}}
\newcommand{\bfthen}{{\bf then}}
\newcommand{\bfelse}{{\bf else}}
\newcommand{\bfret}{{\bf return}}
\newcommand{\bffor}{{\bf for}}
\newcommand{\bfto}{{\bf to}}
\newcommand{\bfwhile}{{\bf while}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                         %%%
%%%  Document starts here...                                                %%%
%%%                                                                         %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

%%%  Here's the command that creates the title bar.  The first argument is the
%%%  handout number; the second argument is the date.



\bigskip

\begin{center}
\LARGE \bf Average Case Analysis of Quicksort
\end{center}

\begin{center}
Javed Aslam, Cheng Li, Virgil Pavlu
\end{center}

We assume that all elements are equally likely to be chosen as the pivot element in {\sc Partition}. When partitioning an array of size $n$ into two subarrays, we have the following possible sizes of the subarrays.
\begin{center}
\begin{tabular}{c c}
left array& right array\\ \hline
$n-1$ &0\\
$n-2$ &1\\
$n-3$ &2\\
$\cdot$&$\cdot$\\
$\cdot$&$\cdot$\\
$\cdot$&$\cdot$\\
1&$n-2$\\
0&$n-1$
\end{tabular}
\end{center}

So we have
\begin{align}
T(n)&=\frac{1}{n}\sum_{j=0}^{n-1}(T(j)+T(n-j-1))+n\\ 
&=\frac{2}{n}\sum_{k=0}^{n-1}T(k)+n\\
&=\frac{2}{n}\sum_{k=1}^{n-1}T(k)+n\text{~~(no recursive call for 0-sized subproblem)} 
\end{align}

Replacing $n$ with $n-1$, we get 
\begin{align}
T(n-1)=\frac{2}{n-1}\sum_{k=1}^{n-2}T(k)+n-1
\end{align}


Multiplying (3) by $n$ and (4) by $n-1$:
\begin{align}
nT(n)&=2\sum_{k=1}^{n-1}T(k)+n^2\\
(n-1)T(n-1)&=2\sum_{k=1}^{n-2}T(k)+(n-1)^2
\end{align}

Subtracting (6) from (5), we get
\begin{align}
&nT(n)-(n-1)T(n-1)=2T(n-1)+2n-1\\
\Longrightarrow & nT(n)=(n+1)T(n-1)+2n-1\\
\Longrightarrow &T(n)=\frac{n+1}{n}T(n-1)+2-\frac{1}{n}.
\end{align}

Ignoring the $1/n$ term in (9), we have
\begin{align}
T(n)\leq \frac{n+1}{n}T(n-1)+2
\end{align}

{\bf Method 1:}
We solve (10) by iteration:

\begin{align*}
T(n)&\leq 2+\frac{n+1}{n}T(n-1)\\
&\leq 2+\frac{n+1}{n}(2+\frac{n}{n-1}T(n-2))\\
&=2+2\frac{n+1}{n}+\frac{n+1}{n-1}+T(n-2)\\
&\leq 2+2\frac{n+1}{n}+\frac{n+1}{n-1}(2+\frac{n-1}{n-2}T(n-3))\\
&=2+2\frac{n+1}{n}+2\frac{n+1}{n-1}+\frac{n+1}{n-2}T(n-3)\\
&=2\frac{n+1}{n+1}+2\frac{n+1}{n}+2\frac{n+1}{n-1}+\frac{n+1}{n-2}T(n-3)\\
&\cdot\\
&\cdot\\
&\cdot\\
&=2(n+1)\sum_{i=0}^{k-1}\frac{1}{(n+1)-i}+\frac{n+1}{n-(k-1)}T(n-k)\\
&=2(n+1)\sum_{i=0}^{n-2}\frac{1}{(n+1)-i}+\frac{n+1}{2}T(1)\\
&=2(n+1)\sum_{j=3}^{n+1}\frac{1}{j}+\frac{n+1}{2}\Theta(1)\\
&=2(n+1)\Theta(\ln n)+\Theta(n)\\
&=\Theta(n\log n)
\end{align*}


{\bf Method 2:} Dividing (10) by $n+1$:
\[
\frac{T(n)}{n+1}\leq \frac{T(n-1)}{n}+\frac{2}{n+1}
\]

Let $R(n)=\frac{T(n)}{n+1}$ (and thus, $R(n-1)=\frac{T(n-1)}{n})$. We have
\[
R(n)\leq R(n-1)+\frac{2}{n+1}
\] 

Note that $R(1)=\frac{T(1)}{1+1}=\Theta(1)$. We get
\begin{align*}
R(n)&\leq \frac{2}{n+1}+\frac{2}{n}+\frac{2}{n-1}+\cdots +\frac{2}{3}+R(1)\\
&=2\sum_{k=3}^{n+1}\frac{1}{k}+\Theta(1)\\
&=\Theta(\ln n)
\end{align*}

Therefore,
\begin{align*}
T(n)&=(n+1)R(n)\\
&=(n+1)\Theta(\ln n)\\
&=\Theta(n\ln n)
\end{align*}
\end{document}