1. Alternative quicksort analysis (problem 7-3 in the text). An alternative analysis of the running time of randomized quicksort focuses on the expected running time of each individial recursive call to Randomized-Quicksort, rather than on the number of comparisons performed. (a) Argue that, given an array of size n, the probability that any particular element is chosen as the pivot is 1=n. Use this to define indicator random variables Xi = Ifith smallest element is chosen as the pivotg What is E[Xi]? (b) Let T (n) be a random variable denoting the running time of quicksort on an array of size n. Argue that E[T (n)] = E "Xq=1 n Xq(T (q − 1) + T (n − q) + Θ(n))# (1) (c) Show that we can rewrite equation 1 as E[T (n)] = 2 n n−1 X q =2 E[T (q)] + Θ(n) (2) (d) Show that n−1 X k =2 k lg k ≤ 1 2 n2 lg n − 1 8 n2 (3) (Hint: Split the summation into two parts, one for k = 2; 3; :::; dn=2e − 1 and one for k = dn=2e; :::; n − 1 (e) Using the bound from equation 3, show that the recurrence in equation 2 has the solution E[T (n)] = Θ(n lg n). (Hint: Show, by substitution, that E[T (n) ≤ an lg n for sufficiently large n and for some positive constant a.) 1
