$(20$ points$)$ We explore a different analysis of the application of random$-$

ized quicksort to an array of size $n.$

$($a$)(2$ points$)$ For iin$[1,n],$ let $x_i$ be the indicator random variable for

the event that the $i$ th smallest number in the array is chosen as the

pivot. That is$,x_i=1$ if this event happens, and $x_i=0$ otherwise.

Derive $E[x_i].$

$($b$)(2$ points$)$ Let $T(n)$ be a random variable that denotes the running

time of randomized quicksort on an array of size $n.$ Prove that

$E[T(n)]=E[{\displaystyle \underset{i=1}{\overset{n}{}}}{x}_i*(T(i-1)+T(n-i)+(n))]$

$($c$)(2$ points$)$ Prove that $E[T(n)]=\frac{2}{n}*{\displaystyle \underset{i=2}{\overset{n-1}{}}}E[T(i)]+(n).$

$($d$)(7$ points$)$ Prove that ${\displaystyle \underset{k=2}{\overset{n-1}{}}}$klogk$\frac{1}{2}{n}^{2}logn-\frac{1}{8}{n}^2.($Hint: Consider

$k=2,3,$dots,$(\frac{n}{2})-1$ and $k=\frac{n}{2},$dots,$n-1$ separately.$)$

$($e$)(7$ points$)$ Use $($d$)$ to show that the recurrence in $($c$)$ yields $E[T(n)]=$

$(nlogn).($Hint: Use substitution to show that $E[T(n)]$cnlogn

for some positive constant $c$ when $n$ is sufficiently large.$)$