New Upper Bounds for Selection

Research output: Contribution to journalArticle

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

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)

Cite this