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 < n/2, then Ui (n) = n + O (T (2i) lg (n/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)..

  • CreatedJuly 13, 2010
  • Files Included
Post your question