$($a$)(0\mathrm{.}2pt)$ Prove by substitution method that the running time of quicksort is $T(n)=O(nlgn)$

for the case that each time partition subroutine generates $\frac{1}{10}$ : $\frac{9}{10}$ split $($i$.$e$.,$ with recurrence

as $\{$:$T(n)=T(\frac{n}{10})+T(\frac{9n}{10})+dn).$

$($b$)(0\mathrm{.}2$pt$)$ Write the recurrence of the worst$-$case running time of Quicksort.

$($c$)(0\mathrm{.}3pt)$ Draw recursion tree and solve the recurrence.

$($d$)(0\mathrm{.}3pt)$ Use substitution method to prove the solution. If the running time derived may be in

$$ notation, you can just prove by treating it as $O$ notation.