9-3 Small order statistics

We showed that the worst-case number $T(n)$ of comparisons used by $\text{SELECT}$ to select the $i$th order statistic from $n$ numbers satisfies $T(n) = \Theta(n)$, but the constant hidden by the $\Theta$-notation is rather large. When $i$ is small relative to $n$, we can implement a different procedure that uses $\text{SELECT}$ as a subroutine but makes fewer comparisons in the worst case.

a. Describe an algorithm that uses $U_i(n)$ comparisons to find the $i$th smallest of $n$ elements, where

$$ U_i(n) = \begin{cases} T(n) & \text{if $i \ge n / 2$}, \\ \lfloor n / 2 \rfloor + U_i(\lceil n / 2 \rceil) + T(2i) & \text{otherwise}. \end{cases} $$

($\textit{Hint:}$ Begin with $\lfloor n / 2 \rfloor$ disjoint pairwise comparisons, and recurse on the set containing the smaller element from each pair.)

b. Show that, if $i < n / 2$, then $U_i(n) = n + O(T(2i)\lg(n / i))$.

c. Show that if $i$ is a constant less than $n / 2$, then $U_i(n) = n + O(\lg n)$.

d. Show that if $i = n / k$ for $k \ge 2$, then $U_i(n) = n + O(T(2n / k)\lg k)$.

(Removed)