CSCI 305, Homework # 6
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 Atime 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 E[T(n)] = E" n X q=1 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
klgk ≤
1 2
n2 lgn− 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)] = Θ(nlgn). (Hint: Show, by substitution, that E[T(n) ≤ anlgn for sufficiently large n and for some positive constant a.
