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 - Funding Information:
This research was supported by the National Science Foundation under grant number GJ-992.
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

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

SN - 0737-8017

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 1972

Y2 - 1 May 1972 through 3 May 1972

ER -