Linear time bounds for median computations

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

Research output: Contribution to journalConference articlepeer-review

31 Scopus citations


New upper and lower bounds are presented for the maximum number of comparisons, f(i,n), required to select the i-th largest of n numbers. An upper bound is found, by an analysis of a new selection algorithm, to be a linear function of n: (Equation presented), A lower bound is shown deductively to be: (Equation presented), or, for the case of computing medians: (Equation presented).

Original languageEnglish (US)
Pages (from-to)119-124
Number of pages6
JournalProceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - May 1 1972
Event4th Annual ACM Symposium on Theory of Computing, STOC 1972 - Denver, United States
Duration: May 1 1972May 3 1972

All Science Journal Classification (ASJC) codes

  • Software

Cite this