The worst case number T(n) of comparisons used by SELECT to select the ith order statistic from n numbers was shown to satisfy 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 SELECT as a su...

a Our algorithm relies on a particular property of SELECT that not only does it return the i th smal ...

The worst-case number T(n) of comparisons used by SELECT to select the ith order statistic from n

Question:

The worst-case number T(n) of comparisons used by SELECT to select the ith order statistic from n numbers was shown to satisfy T(n) = Θ(n), but the constant hidden by the Θ-notation is rather large. When i is small relative to n, we can implement a different procedure that uses SELECT as a subroutine but makes fewer comparisons in the worst case.
a. Describe an algorithm that uses Ui (n) comparisons to find the ith smallest of n elements, where.

b. Show that, if i c. Show that if i is a constant less than n/2, then Ui (n) = n + O (lg n)..
d. Show that if i = n/k for k ≥ 2, then Ui (n) = n + O (T (2n/k) lg k)..