Time bounds for selection

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

doi:10.1016/S0022-0000(73)80033-9

Time bounds for selection

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

Research output: Contribution to journal › Article › peer-review

948 Scopus citations

Abstract

The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm-PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.

Original language	English (US)
Pages (from-to)	448-461
Number of pages	14
Journal	Journal of Computer and System Sciences
Volume	7
Issue number	4
DOIs	https://doi.org/10.1016/S0022-0000(73)80033-9
State	Published - Aug 1973
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/S0022-0000(73)80033-9

Cite this

@article{f47a6b490ce34b9d8129e9d0fdab9eb2,

title = "Time bounds for selection",

abstract = "The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm-PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.",

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

note = "Funding Information: work was supported by the National Science Foundation under grant GJ-992.",

year = "1973",

month = aug,

doi = "10.1016/S0022-0000(73)80033-9",

language = "English (US)",

volume = "7",

pages = "448--461",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "4",

}

TY - JOUR

T1 - Time bounds for selection

AU - Blum, Manuel

AU - Floyd, Robert W.

AU - Pratt, Vaughan

AU - Rivest, Ronald L.

AU - Tarjan, Robert E.

N1 - Funding Information: work was supported by the National Science Foundation under grant GJ-992.

PY - 1973/8

Y1 - 1973/8

N2 - The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm-PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.

AB - The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm-PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.

UR - https://www.scopus.com/pages/publications/0015865168

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

U2 - 10.1016/S0022-0000(73)80033-9

DO - 10.1016/S0022-0000(73)80033-9

M3 - Article

AN - SCOPUS:0015865168

SN - 0022-0000

VL - 7

SP - 448

EP - 461

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 4

ER -

Time bounds for selection

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this