Question: In this problem, we use indicator random variables to analyze the RANDOMIZED SELECT procedure in a manner akin to our analysis of RANDOMIZED-QUICKSORT in Section
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 i th smallest element. Thus, the call RANDOMIZED-SELECT ( A, 1, n, k) returns zk. For 1 ¤ i < j ¤ n, let Xijk = I {zi is compared with zj sometime during the execution of the algorithm to find zk}.
a. Give an exact expression for E [Xijk]. Your expression may have different values, depending on the values of i, j, and k.
b. Let Xk denote the total number of comparisons between elements of array A when finding zk. Show that
c. Show that E [Xk] ¤ 4n.
d. Conclude that, assuming all elements of array A are distinct, RANDOMIZED SELECT runs in expected time O(n).
j k 1 j - k +1 k k i 1 E[X&] < 2(EE: j - i +1 i=1 j=k k i +1 i=1 j=k+1
Step by Step Solution
3.53 Rating (173 Votes )
There are 3 Steps involved in it
a As in the quicksort analysis elements z i and z j will not be compared with each other if any element in z i 1 z i 2 z j 1is chosen as a pivot element before eitherz i or z j becausez i and z j woul... View full answer

Get step-by-step solutions from verified subject matter experts