@InProceedings{BFPRT72,
replaced-by = { BFPRT73 },
author = { Manuel Blum and Robert W. Floyd and Vaughan Pratt and Ronald L. Rivest and Robert E. Tarjan },
title = { Linear time bounds for median computations },
pages = { 119--124 },
acm = { 08028 },
doi = { 10.1145/800152.804904 },
acmid = { 804904 },
booktitle = { Proceedings of the fourth annual ACM symposium on Theory of Computing },
publisher = { ACM },
date = { 1972-05 },
OPTyear = { 1972 },
OPTmonth = { May 1--3, },
editor = { Patrick C. Fischer and H. Paul Zeiger and Jeffery D. Ullman and Arnold L. Rosenberg },
eventtitle = { STOC'72 },
eventdate = { 1972 },
venue = { Denver, Colorado },
abstract = {
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$: $f(i,n) \le 103n/18 \le 5.73 n$, for $1 \le i \le n$.
A lower bound is shown deductively to be $f(i,n) \ge n + \min(i,n-i+1) +
\ceil{\log_2(n)} - 4$, for $2\le i \le n-1$, or for the case of computing
medians: $ f([n/2],n) \ge 3n/2 - 3 $ .
},
}