Time bounds for selection

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

• Book ID: 104148109
• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 957 KB
• Volume: 7
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(73)80033-9

✦ Synopsis

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.