# 9.2 Selection in expected linear time

## 9.2-1

Show that $\text{RANDOMIZED-SELECT}$ never makes a recursive call to a $0$-length array.

Calling a $0$-length array would mean that the second and third arguments are equal. So, if the call is made on line 8, we would need that $p = q - 1$, which means that $q - p + 1 = 0$.

However, $i$ is assumed to be a nonnegative number, and to be executing line 8, we would need that $i < k = q - p + 1 = 0$, a contradiction. The other possibility is that the bad recursive call occurs on line 9. This would mean that $q + 1 = r$. To be executing line 9, we need that $i > k = q - p + 1 = r - p$. This would be a nonsensical original call to the array though because we are asking for the ith element from an array of strictly less size.

## 9.2-2

Argue that the indicator random variable $X_k$ and the value $T(\max(k - 1, n - k))$ are independent.

The probability that $X_k$ is equal to $1$ is unchanged when we know the max of $k - 1$ and $n - k$. In other words, $\Pr\{X_k = a \mid \max(k - 1, n - k) = m\} = \Pr\{X_k = a\}$ for $a = 0, 1$ and $m = k - 1, n - k$ so $X_k$ and $\max(k - 1, n - k)$ are independent.

By C.3-5, so are $X_k$ and $T(\max(k - 1, n - k))$.

## 9.2-3

Write an iterative version of $\text{RANDOMIZED-SELECT}$.

1 2 3 4 5 6 7 8 9 10 | PARTITION(A, p, r) x = A[r] i = p for k = p - 1 to r if A[k] < x i = i + 1 swap A[i] with A[k] i = i + 1 swap A[i] with A[r] return i |

1 2 3 4 | RANDOMIZED-PARTITION(A, p, r) x = RANDOM(p - 1, r) swap A[x] with A[r] return PARTITION(A, p, r) |

1 2 3 4 5 6 7 8 9 10 11 12 13 | RANDOMIZED-SELECT(A, p, r, i) while true if p == r return A[p] q = RANDOMIZED-PARTITION(A, p, r) k = q - p + 1 if i == k return A[q] if i < k r = q else p = q i = i - k |

## 9.2-4

Suppose we use $\text{RANDOMIZED-SELECT}$ to select the minimum element of the array $A = \langle 3, 2, 9, 0, 7, 5, 4, 8, 6, 1 \rangle$. Describe a sequence of partitions that results in a worst-case performance of $\text{RANDOMIZED-SELECT}$.

When the partition selected is always the maximum element of the array we get worst-case performance. In the example, the sequence would be $\langle 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 \rangle$.