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 7.4.2.

As in the quicksort analysis, we assume that all elements are distinct, and we rename the elements of the input array A as z₁, z₂, . . . ,z_n, where z_i is the i th smallest element. Thus, the call RANDOMIZED-SELECT ( A, 1, n, k) returns z_k. For 1 ‰¤ i < j ‰¤ n, let X_ijk = I {z_i is compared with z_j sometime during the execution of the algorithm to find z_k}.

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

b. Let X_k denote the total number of comparisons between elements of array A when finding z_k. Show that

c. Show that E [X_k] ‰¤ 4n.

d. Conclude that, assuming all elements of array A are distinct, RANDOMIZED SELECT runs in expected time O(n).

Transcribed Image Text:

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