A Counting Approach to Lower Bounds for Selection Problems
Frank Fussenegger, Harold N. Gabow · Journal of the ACM · 1979
Lower bounds are derived on the number of comparisons to solve several well-known selection problems Among the problems are finding the t largest elements of a given set m order (Wt), finding the s smallest and t largest elements in order (We.t), and finding the tth largest element (Vt) The results follow from bounds for more general selection problems, where an arbitrary partml order is given The bounds for Wt and Vt generahze to the case where comparisons between hnear functions of the input are allowedThe approach is to show that a comparison tree for a selection problem contains a number of trees for smaller problems, thus estabhshmg a lower bound on the number of leaves An equivalent approach uses an adversary, based on a numerical "chaos" function that measures the number of unknown relations KEY WORDS AND PHRASES selection problems, lower bounds, comparisons, comparison trees CR CATEGORIES 5 25, 5 31 Ut: Fred the t largest elements as a set.(For t = [kn/lOOJ, the problem is to find the elements in the upper k percentiles.)W~.t: Find the s smallest and t largest elements in order.(For s --t = l, the problem is to find the maximum and the minimum.)We mvesugate the worst-case number of comparisons needed to solve selection problems.For this, the function Wt(n) is defined as the number of comparisons needed to find the t largest elements: slmdar functions are used for the other selection problems.(Occasionally, we use Wt(n) to refer to the Wt problem on n elements; no confusion results from this )