The Random Quicksort algorithm works as follows. We assume that the numbers are pairwise different.

(a) If the array has one element or is empty return the array

(b) Otherwise choose a number at random from A[1], A[2], . . . , A[n]. This number is called a pivot. Let x be the value of the chosen entry

(c) Create an array AS of all elements smaller than x, and AL the elements that are larger than x

(d) Recursively sort AS and AL and return AS, x, AL. Let B[1], B[2], . . . , B[n] be the array A sorted, namely B[i] is the ith smallest number in A.

Let Xij be the random variable that has value of 1 if B[i] and B[j] are compared, and has value 0 otherwise. Let T be the number of comparisons in Random Quicksort

(a) Show that T = Pn i=1 P j>i Xij .

(b) Show that if B[p] for p < i or p > j is chosen as pivot this does not change the probability that B[i] and B[j] will be compared.

(c) Show that if the first element chosen as pivot among B[i], B[i+1], . . . , B[j] is A[p] for i < p < j, then Xij = 0 (B[i] and B[j] are not compared).

(d) Show that the probability that B[i], B[j] are compared is 2/(j i + 1),

(e) Show that E(T) = Pn i=1 P j>i 2/(j i + 1).

(f) Show that for i = 1, P j>1 P(B[1] and B[i] are compared) = 2(1 + 1/2 + 1/3 + 1/4 + . . . 1/n) = 2 ln n + (1).

(g) Show that E(T) 2 n ln n + O(n).