New Upper Bounds for Selection The worst-case minimum number of comparisons complexity Vi(n) of the i-th selection problem is considered. A new upper bound for Vi(n) improves the bound given by the standard Hadian-Sobel algorithm by a generalization of the Kirkpatrick-Hadian-Sobel algorithm, and extends Kirkpatrick's method to a much wider range of application. This generalization compares favorably with a recent algorithm by Hyafil. CACM September, 1976 Yap, C. K. selection problem, algorithms, comparison problems, concrete computational complexity, upper bounds, worst-case analysis 5.25 5.31 CA760902 JB January 4, 1978 9:48 AM 2837 4 2837 2837 4 2837 3150 4 2837 2784 5 2837 2837 5 2837 2837 5 2837 2837 5 2837 2842 5 2837