The problem of finding the k-th element is that, given an unsorted array to A[1n], find the k-th element when all the elements are sorted. The problem finding the median is a special case of this problem for k = ?n/2?.

Consider the following idea on finding the k-th element (called RandSelect):

Randomly pick an element as the pivot.

Partition the array around the pivot (same as the partitioning in quick sort, with the pivot in the middle, smaller elements in the left part, and larger elements in the right part).

Let l be the index of the pivot:

If l = k, return the pivot;

If l < k, recurse to find the (k - l)-th element in the right part

If l > k, recurse to find the k-th element in the left part

In this problem, we use indicator random variables to analyze the RandSelect procedure in a manner akin to our analysis of RandQuickSort in class.

As in the quicksort analysis, we assume that all elements are distinct, and we rename the elements of the input array A as z1, z2, , zn, where zi is the ith smallest element. Thus, the call RandSelect(A, 1, n, k) returns zk.

For 1 < i < j < n, let

Xijk = I {zi is compared with zj some time during the execution of the algorithm to find zk}.

(a) Give an exact expression for E[ Xijk ]. (Hint: Your expression may have different values, depending on the values of i, j, and k.)

(b) Let Yk denote the total number of comparisons between elements of array A when finding zk. Show that

E[ Yk ] ? 2 ( ?i=1...k ?j=k...n [1/(j-i+1)] + ?j=k+1...n [(j-k-1)/(j-k+1)] + ?i=1...k-2[(k-i-1)/(k-i+1)]

(c) Show that E[ Yk ] ? 4n.