Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 501-508 |
Number of pages | 8 |
Journal | Communications of the ACM |
Volume | 19 |
Issue number | 9 |
DOIs | |
State | Published - Sep 1 1976 |
Keywords
- algorithms
- comparison problems
- concrete computational complexity
- selection problem
- upper bounds
- worst-case analysis
ASJC Scopus subject areas
- General Computer Science