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

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}, \ldots, z_{j - 1}\}$ is chosen as a pivot element before either $z_i$ or $z_j$, because $z_i$ and $z_j$ would then lie in separate partitions. There can be another reason that $z_i$ and $z_j$ might not be compared, however. Suppose that $k < i$, so that $z_k < z_i$ , and suppose further that the element chosen as the pivot is $z_l$, where $k \le l < i$. In this case, because $k \le l$, the recursion won't consider elements indexed higher than $l$. Therefore, the recursion will never look at $z_i$ or $z_j$ , and they will never be compared with each other. Similarly, if $j < k$ and the pivot element $z_l$ is such that $j < l \le k$, then the recursion won't consider elements indexed less than $l$, and again $z_i$ and $z_j$ will never be compared with each other. The final case is when $i \le k \le j$ (but disallowing $i = j$), so that $z_i \le z_k \le z_j$; in this case, we have the same analysis as for quicksort: $z_i$ and $z_j$ are compared with each other only if one of them is chosen as the pivot element.

Getting back to the case in which $k < i$, it is again true that $z_i$ and $z_j$ are compared with each other only if one of them is chosen as the pivot element. As we know, they won't be compared with each other if the pivot element is between them, and we argued above that they won't be compared with each other if the pivot element is $z_l$ for $l < i$. Similarly, when $j < k$, elements $z_i$ and $z_j$ are compared with each other only if one of them is chosen as the pivot element.

Now we need to compute the probability that $z_i$ and $z_j$ are compared with each other. Let $Z_{ijk}$ be the set of elements that includes $z_i, \ldots, z_j$, along with $z_k, \ldots, z_{i - 1}$ if $k < i$ or $z_{j + 1}, \ldots, z_k$ if $j < k$. In other words,

$$ Z_{ijk} = \begin{cases} {z_i, z_{i + 1}, \ldots, z_j} & \text{if $i \le k \le j$}, \\ {z_k, z_{k + 1}, \ldots, z_j} & \text{if $k < i$}, \\ {z_i, z_{i + 1}, \ldots, z_k} & \text{if $j < k$}. \end{cases} $$

With this definition of $Z_{ijk}$, we have that

$$|Z_{ijk}| = \max(j - i + 1, j - k + 1, k - i + 1).$$

As in the quicksort analysis, we observe that until an element from $Z_{ijk}$ is chosen as the pivot, the whole set $Z_{ijk}$ is together in the same partition, and so each element of $Z_{ijk}$ is equally likely to be the first one chosen as the pivot.

Letting $C$ be the event that $z_i$ is compared with $z_j$ during the execution of the algorithm, we have that

$$ \begin{aligned} \text E[X_{ijk}] & = \Pr\{C\} \\ & = \Pr\{z_i \text{ or } z_j \text{ is the first pivot chosen from } Z_{ijk}\} \\ & = \Pr\{z_i \text{ is the first pivot chosen from } Z_{ijk}\} + \Pr\{z_j \text{ is the first pivot chosen from } Z_{ijk}\} \\ & = \frac{1}{|Z_{ijk}|} + \frac{1}{|Z_{ijk}|} \\ & = \frac{2}{\max(j - i + 1, j - k + 1, k - i + 1)}. \end{aligned} $$

b. Adding up all the possible pairs that might be compared gives

$$X_k = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^n X_{ijk},$$

and so, by linearity of expectation, we have

$$ \begin{aligned} \text E[X_k] & = \text E \Bigg[\sum_{i = 1}^{n - 1}\sum_{j = i + 1}^n X_{ijk} \Bigg] \\ & = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^n \text E[X_{ijk}] \\ & = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^n \frac{2}{\max(j - i + 1, j - k + 1, k - i + 1)}. \end{aligned} $$

We break this sum into the same three cases as before: $i \le k \le j$, $k < i$ and $j < k$. With $k$ fixed, we vary $i$ and $j$. We get an inequality because we cannot have $i = k = j$, but our summation will allow it:

$$ \begin{aligned} \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 \sum_{i = k + 1}^{j - 1} \frac{1}{j - k + 1} + \sum_{i = 1}^{k - 2} \sum_{j = i + 1}^{k - 1} \frac{1}{k - i + 1}\Bigg) \\ & = 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). \end{aligned} $$

c. First, let's focus on the latter two summations. Each one sums fractions that are strictly less than 1. The middle summation has $n - k$ terms, and the right-hand summation has $k - 2$ terms, and so the latter two summations sum to less than $n$.

Now we look at the first summation. Let $m = j - i$. There is only one way for $m$ to equal $0$: if $i = k = j$. There are only two ways for $m$ to equal $1$: if $i = k - 1$ and $j = k$, or if $i = k$ and $j = k + 1$. There are only three ways for $m$ to equal $2$: if $i = k - 2$ and $j = k$, if $i = k - 1$ and $j = k + 1$, or if $i = k$ and $j = k + 2$. Continuing on, we see that there are at most $m + 1$ ways for $j - i$ to equal $m$. Since $j - i \le n - 1$, we can rewrite the first summation as

$$\sum_{m = 0}^{n - 1} \frac{m + 1}{m + 1} = n.$$

Thus, we have

$$ \begin{aligned} \text E[X_k] & < 2(n + n) \\ & = 4n. \end{aligned} $$

d. To show that $\text{RANDOMIZED-SELECT}$ runs in expected time $O(n)$, we adapt Lemma 7.1 for $\text{RANDOMIZED-SELECT}$. The adaptation is trivial: just replace the variable $X$ in the lemma statement by the random variable $X_k$ that we just analyzed. Thus, the expected running time of $\text{RANDOMIZED-SELECT}$ is $O(n + X_k) = O(n)$.