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