@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 $ .                  
                 },
}