9-4 Alternative analysis of randomized selection

In this problem, we use indicator random variables to analyze the $\text{RANDOMIZED-SELECT}$ procedure in a manner akin to our analysis of $\text{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_1, z_2, \ldots, z_n$, where $z_i$ is the $i$th smallest element. Thus, the call $\text{RANDOMIZED-SELECT}(A, 1, n, k)$ returns $z_k$.

For $1 \le i < j \le n$, let

$$X_{ijk} = \text{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 $\text E[X_{ijk}]$. ($\textit{Hint:}$ 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

$$\text E[X_k] \le 2 \Bigg (\sum_{i = 1}^{k}\sum_{j = k}^n \frac{1}{j - i + 1} + \sum_{j = k + 1}^{n} \frac{j - k - 1}{j - k + 1} + \sum_{i = 1}^{k-2} \frac{k - i - 1}{k - i + 1} \Bigg).$$

c. Show that $\text E[X_k] \le 4n$.

d. Conclude that, assuming all elements of array $A$ are distinct, $\text{RANDOMIZED-SELECT}$ runs in expected time $O(n)$.

(Removed)