(20 points, from textbook) We explore a different analysis of the applica- tion of randomized quicksort to an array of size n. (a) (2 points) For i = [1, n], let X be the indicator random variable for the event that the ith smallest number in the array is chosen as the pivot. That is, X = 1 if this event happens, and X = 0 otherwise. Derive E[X]. (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 n .(n))]. E[T(n)] = E | X; (T(i 1) + T(n i) + O(n)) - (c) (2 points) Prove that E[T(n)] = E[T(i)] + (n). n - (d) (7 points) Prove that k log k n log nn. (Hint: Consider k = 2, 3, . . ., (n/2) 1 and k = n/2, ..., n 1 separately.) - = (e) (7 points) Use (d) to show that the recurrence in (c) yields E[T(n)] O(nlogn). (Hint: Use substitution to show that E[T(n)] < cn log n for some positive constant c when n is sufficiently large.)