New Upper Bounds for Selection

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)501-508
Number of pages8
JournalCommunications of the ACM
Issue number9
StatePublished - Sep 1 1976


  • algorithms
  • comparison problems
  • concrete computational complexity
  • selection problem
  • upper bounds
  • worst-case analysis

ASJC Scopus subject areas

  • General Computer Science

Cite this