Solved: In this exercise we find the average-case

Chapter 6, Problem 6.4.36

(choose chapter or problem)

In this exercise we find the average-case complexity of the quick sort algorithm, described in the preamble to Exercise 50 in Section 4.4, assuming a uniform distribution on the set of permutations. a) Let X be the number of comparisons used by the quick sort algorithm to sort a list of n distinct integers. Show that the average number of comparisons used by the quick sort algorithm is E(X) (where the sample space is the set of all n! permutations of n integers). b) Let Ij,k denote the random variable that equals 1 if the ith smallest element and the kth smallest element of the initial list are ever compared as the quick sort algorithm sorts the list and equals 0 otherwise. Show that X = L=2 L:: Ij,k. c) Show that E(X) = L=z L:: p (the ith smallest element and the kth smallest element are compared). d) Show that p (the ith smallest element and the kth smallest element are compared), where k > i, equals 2/(k - i + 1). e) Use parts (c) and (d) to show that E(X) = 2(n + I)(L7=2 Ili) - 2(n - 1). I) Conclude from part (e) and the fact that L=' Iii :::::: In n + y, where y = 0.57721 ... is Euler's constant, that the average number of comparisons used by the quick sort algorithm is B(n log n).