Time bounds for selection
โ
Manuel Blum; Robert W. Floyd; Vaughan Pratt; Ronald L. Rivest; Robert E. Tarjan
๐
Article
๐
1973
๐
Elsevier Science
๐
English
โ 957 KB
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