9.2 Selection in expected linear time

9.2-1

If an array has 0 length, we have q - p = 0 or r - q = 0. If q - p = 0, we have k = 1 and line 8 will be executed, but we have i < k, so i < 1, which is not possible. If r - q = 0, we have i > k, but k = q - p + 1 = r - p + 1, so k is the length of array, thus i could not be larger than k.

So the algorithm never makes a recursive call to a 0-length array.

9.2-2

The value of $X_k$ doesn't affect the subproblem T(max(k - 1, n - k)). So they are independent.

9.2-3

RANDOMIZED-SELECT(A, p, r, i)

while p <= r
    if p == r
        return A[p]
    q = RANDOMIZED-PARTITION(A, p, r)
    k = q - p + 1
    if i = k
        return A[q]
    elseif i < k
        r = q - 1
    else
        p = q + 1
        i = i - k

9.2-4

The worst-case happens when the partition procedure always select the largest element as pivot.

pivot = 9, subarray = { 3, 2, 1, 0, 7, 5, 4, 8, 6}
pivot = 8, subarray = { 3, 2, 1, 0, 7, 5, 4, 6 }
pivot = 7, subarray = { 3, 2, 1, 0, 6, 5, 4 }
pivot = 6, subarray = { 3, 2, 1, 0, 4, 5 }
pivot = 5, subarray = { 3, 2, 1, 0, 4}
pivot = 4, subarray = { 3, 2, 1, 0 }
pivot = 3, subarray = { 0, 2, 1 }
pivot = 2, subarray = { 0, 1 }
pivot = 1, subarray = { 0 }
minimum = 0