Chapter 9.2

If we make a recursive call to \(0\)-length array in line 8, then we have \(q - 1 < p\), and \(i < k = q - p + 1\), thus we have \(i < 1\), which is illegal.

If we make a recursive call to \(0\)-length array in line 9, then we have \(r < q + 1\), and \(i > k = q - p + 1\), thus we have \(i > r - p + 1\), which is illegal.

Thus, RANDOMIZED-SELECT never makes a recursive call to a \(0\)-length array.

The value \(T(max(k-1,n-k))\) does not affect the indicator random variable \(X_k\), and the \(X_k\) does not affect \(T(max(k-1,n-k))\) either, thus they are independent.

RANDOMIZED-SELECT-ITER(A, i)
    p = 1
    r = A.length
    while r > p
        q = RANDOMIZED-PARTITION(A, p, r)
        k = q - p + 1
        if i == k
            return A[q]
        else if i < k
            r = q - 1
        else p = q + 1
             i = i - k
    return A[p]

The sequence of partitions results in a worst-case performance of RANDOMIZED-SELECT, if we always choose the maximum element of the subarray as the pivot.