Time bounds for selection

Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

749 Scopus citations

Abstract

The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm-PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.

Original languageEnglish (US)
Pages (from-to)448-461
Number of pages14
JournalJournal of Computer and System Sciences
Volume7
Issue number4
DOIs
StatePublished - Aug 1973

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Time bounds for selection'. Together they form a unique fingerprint.

Cite this