Time bounds for selection

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

Research output: Contribution to journalArticlepeer-review

868 Scopus citations


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
Issue number4
StatePublished - Aug 1973
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


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

Cite this