TY - JOUR
T1 - Linear time bounds for median computations
AU - Blum, Manuel
AU - Floyd, Robert W.
AU - Pratt, Vaughan
AU - Rivest, Ronald L.
AU - Tarjan, Robert E.
N1 - Publisher Copyright:
© 1972 Association for Computing Machinery. All rights reserved.
PY - 1972/5/1
Y1 - 1972/5/1
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=85044561541&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85044561541&partnerID=8YFLogxK
U2 - 10.1145/800152.804904
DO - 10.1145/800152.804904
M3 - Conference article
AN - SCOPUS:85044561541
SN - 0737-8017
SP - 119
EP - 124
JO - Proceedings of the Annual ACM Symposium on Theory of Computing
JF - Proceedings of the Annual ACM Symposium on Theory of Computing
T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 1972
Y2 - 1 May 1972 through 3 May 1972
ER -