A Counting Approach to Lower Bounds for Selection Problems ; CU-CS-107-77

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, in order (Wt); finding the s smallest and t largest elements, in order (Ws,t); and finding the tth largest element (Vt). The results follow from bounds for more general selection problmes, where an arbitrary partial order is given. The bounds for Wt and Vt generalize to the case where comparisons between linear functions of the input are allowed. The approach is to show a comparison tree for a selection problem contains a number of trees for smaller problems, thus establishing 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