$7$ Bonus! Analyzing quickSort

In this bonus section you will work through the analysis of the expected running time of everybody's favorite

sorting algorithm: quickSort. Here is some pseudocode.

Input: An integer array $A$ of length $n.$ Assume for simplicity that every integer in $A$ is unique.

Base Case: If $n=1,$ return $A.$

Choose the Pivot: Choose a random index $i\{0,1,$dots,$n-1\}$ and let $p=A[i].$

Filter Around the Pivot: Let s$.$t$.x>p{A}_{0}Ap$;$A_{1}A{B}_0=(A_0)B_1=(A_1)B=B_0+[p]+B_1-e.g.,\left[\begin{array}{cc}1& 2\end{array}\right]+\left[\begin{array}{cc}3& 4\end{array}\right]=\left[\begin{array}{cccc}1& 2& 3& 4\end{array}\right].T_{n}An{T}_n=O(nlogn)p(k+1)ABB[k]A_{0}k{A}_{1}n-k-1T_k+T_{n-k-1}p(k+1)-A\frac{1}{n}k=0,$dots,$n-1\frac{1}{n}{\displaystyle \underset{k=0}{\overset{n-1}{}}}(T_k+T_{n-k-1})O(1)O(n)T_n{T}_n=cn+\frac{1}{n}{\displaystyle \underset{k=0}{\overset{n-1}{}}}(T_k+T_{n-k-1}).T_1=1n*T_n=c{n}^2+2{\displaystyle \underset{k=0}{\overset{n-1}{}}}{T}_{k}n*T_n=c(2n-1)+(n+1)*T_{n-1}\frac{T_n}{n+1}\frac{2c}{n+1}+\frac{T_{n-1}}{n}.\frac{T_n}{n+1}2c(\frac{1}{n+1}+\frac{1}{n}+$cdots$+\frac{1}{3})+\frac{1}{2}1+\frac{1}{2}+\frac{1}{3}+$cdots$+\frac{1}{n}=O(logn)T_n=O(nlogn)x$ and $A_1=[xinAs.t.x>p].$

$So{A}_0$ consists $of$ all elements $in$ A which are less than $p$;$A_{1}is$ all elements $in$ A which are greater.

Recursive calls: Let $B_0=$ quickSort $(A_0)$ and $B_1=$ quickSort $(A_1).$

Output: Return $B=B_0+[p]+B_1,$ where here $\text{'}+\text{'}$ denotes array concatenation

$-e.g.,\left[\begin{array}{cc}1& 2\end{array}\right]+\left[\begin{array}{cc}3& 4\end{array}\right]=\left[\begin{array}{cccc}1& 2& 3& 4\end{array}\right].$

Computing the runtime $of$ quickSort $is$ conceptually very similar $to$ the runtime computation $of$ mergeSort,

however complications arise because the pivot $is$ chosen randomly. Let $T_n$ denote the expected running time

$of$ quickSort when the input array A has size $n.$ Complete the following outline proving that $T_n=O(nlogn).$

$(a)(Nothingto$ prove here$)$ Suppose that $pis$ the $(k+1)-th$ smallest element $inA,so$ that the pivot

appears $inBatB[k].In$ this case, the length $of{A}_{0}isk$ and the length $of{A}_{1}isn-k-1,$ and $so$

the expected runtime $of$ the recursive calls made $in$ Step $4is{T}_k+T_{n-k-1}.$ Because the pivot was

chosen randomly, the probability that $pis$ indeed the $(k+1)-th$ smallest element $inAis\frac{1}{n}$ for

all $k=0,$dots,$n-1.$ Therefore, the expected runtime $of$ the recursive calls $is\frac{1}{n}{\displaystyle \underset{k=0}{\overset{n-1}{}}}(T_k+T_{n-k-1}).$

Finally, choosing the pivot takes time $O(1)$ and the filter step takes time $O(n).$ Thus, $T_n$ satisfies:

$T_n=cn+\frac{1}{n}{\displaystyle \underset{k=0}{\overset{n-1}{}}}(T_k+T_{n-k-1}).$

This will $be$ our starting point. Also, note $T_1=1.$

$(b)$ Prove $n*T_n=c{n}^2+2{\displaystyle \underset{k=0}{\overset{n-1}{}}}{T}_k.$

$(c)$ Deduce $n*T_n=c(2n-1)+(n+1)*T_{n-1}.$

$(d)$ Deduce

$\frac{T_n}{n+1}\frac{2c}{n+1}+\frac{T_{n-1}}{n}.$

$(e)$ Now iterate this bound $to$ get $\frac{T_n}{n+1}2c(\frac{1}{n+1}+\frac{1}{n}+$cdots$+\frac{1}{3})+\frac{1}{2}.$

$(f)$ Finally use the fact from calculus: $1+\frac{1}{2}+\frac{1}{3}+$cdots$+\frac{1}{n}=O(logn)to$ get $T_n=O(nlogn).$