Linear time bounds for median computations

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

doi:10.1145/800152.804904

Linear time bounds for median computations

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

Research output: Contribution to journal › Conference article › peer-review

33 Scopus citations

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: (Equation presented), A lower bound is shown deductively to be: (Equation presented), or, for the case of computing medians: (Equation presented).

Original language	English (US)
Pages (from-to)	119-124
Number of pages	6
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/800152.804904
State	Published - May 1 1972
Event	4th Annual ACM Symposium on Theory of Computing, STOC 1972 - Denver, United States Duration: May 1 1972 → May 3 1972

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/800152.804904

Cite this

@article{6247b1558d1546e899c2b7e8c9c0c76a,

title = "Linear time bounds for median computations",

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: (Equation presented), A lower bound is shown deductively to be: (Equation presented), or, for the case of computing medians: (Equation presented).",

author = "Manuel Blum and Floyd, \{Robert W.\} and Vaughan Pratt and Rivest, \{Ronald L.\} and Tarjan, \{Robert E.\}",

note = "Publisher Copyright: {\textcopyright} 1972 Association for Computing Machinery. All rights reserved.; 4th Annual ACM Symposium on Theory of Computing, STOC 1972 ; Conference date: 01-05-1972 Through 03-05-1972",

year = "1972",

month = may,

day = "1",

doi = "10.1145/800152.804904",

language = "English (US)",

pages = "119--124",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

}

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.

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 - https://www.scopus.com/pages/publications/85044561541

UR - https://www.scopus.com/pages/publications/85044561541#tab=citedBy

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 -

Linear time bounds for median computations

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this