# In this problem, we use indicator random variables to analyze the RANDOMIZED SELECT procedure in a manner akin to our

## 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 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 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).

## This problem has been solved!

Related Book For ## Introduction to Algorithms

ISBN: 978-0262033848

3rd edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Question Details
Chapter # 9
Section: Problem
Problem: 4
View Solution