(a)

(0.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

(1)/(10)

:

(9)/(10)

split (i.e., with recurrence\ as

{:T(n)=T((n)/(10))+T((9n)/(10))+dn)

.\ (b) (0.2pt) Write the recurrence of the worst-case running time of Quicksort.\ (c)

(0.3pt)

Draw recursion tree and solve the recurrence.\ (d)

(0.3pt)

Use substitution method to prove the solution. If the running time derived may be in\

\\\\theta

notation, you can just prove by treating it as

O

notation.

(a) (0.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 1/10 : 9/10 split (i.e., with recurrence as T(n)=T(10n)+T(109n)+dn). (b) (0.2pt) Write the recurrence of the worst-case running time of Quicksort. (c) (0.3pt) Draw recursion tree and solve the recurrence. (d) (0.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