Description

YOUR NAME HERE
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 = I{ith smallest element is chosen as the pivot}
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
(1)
(c) Show that we can rewrite equation 1 as
) (2)
(d) Show that
(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 solutionE[T(n)] = Θ(nlgn). (Hint: Show, by substitution, that E[T(n) ≤ anlgn for sufficiently large n and for some positive constant a.)
1