Small order statistics We showed that the worst-case

Chapter 9, Problem 9-3

(choose chapter or problem)

Small order statistics We showed that the worst-case number T .n/ of comparisons used by SELECT to select the ith order statistic from n numbers satisfies T .n/ D .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. 226 Chapter 9 Medians and Order Statistics a. Describe an algorithm that uses Ui.n/ comparisons to find the ith smallest of n elements, where Ui.n/ D ( T .n/ if i n=2 ; bn=2c C Ui.dn=2e/ C T .2i / otherwise : (Hint: Begin with bn=2c disjoint pairwise comparisons, and recurse on the set containing the smaller element from each pair.) b. Show that, if i < n=2, then Ui.n/ D n C O.T .2i /lg.n= i //. c. Show that if i is a constant less than n=2, then Ui.n/ D n C O.lg n/. d. Show that if i D n=k for k 2, then Ui.n/ D n C O.T .2n=k/lg k/.