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)..

Transcribed Image Text:

if i z n/2. (T(n) In/2] + U,([n/21) + T (2i) otherwise. U,(n) = U,(n)