Exponential bounds for the running time of a selection algorithm. (English) Zbl 0555.68018

Hoare’s selection algorithm for finding the kth-largest element in a set of n elements is shown to use C comparisons where (i) \(E(C^ p)\leq A_ pn^ p\) for some constant \(A_ p>0\) and all \(p\geq 1\); (ii) P(C/n\(\geq u)\leq (3/4)^{u(1+o(1))}\) as \(u\to \infty\). Exact values for the \(''A_ p''\) and ”o(1)” terms are given.


68Q25 Analysis of algorithms and problem complexity


Algorithm 489; Find
Full Text: DOI


[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass. · Zbl 0286.68029
[2] Blum, M.; Floyd, R. W.; Pratt, V.; Rivest, R. L.; Tarjan, R. E., Time bounds for selection, J. Comput. System Sci., 7, 448-461 (1973) · Zbl 0278.68033
[3] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statist., 23, 493-507 (1952) · Zbl 0048.11804
[4] Chow, Y. S.; Teicher, H., Probability Theory (1978), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0399.60001
[5] Floyd, R. W.; Rivest, R. L., Expected time bounds for selection, Comm. ACM, 18, 165-172 (1975) · Zbl 0296.68049
[6] Floyd, R. W.; Rivest, R. L., Algorithm 489, Comm. ACM, 18, 173 (1975)
[7] Hoare, C. A.R., Find (algorithm 65), Comm. ACM, 4, 321-322 (1961)
[8] Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 13-30 (1963) · Zbl 0127.10602
[9] Horowitz, E.; Sahni, S., Fundamentals of Computer Algorithms (1978), Computer Science Press: Computer Science Press Potomac, Md. · Zbl 0442.68022
[10] Knuth, D. E., Mathematical Analysis of Algorithms, (Computer Science Dept. Report STAN-CS-71-206 (1971), Stanford University) · Zbl 0191.17903
[11] Schonhage, A.; Paterson, M.; Pippenger, N., Finding the median, J. Comput. System Sci., 13, 184-199 (1976) · Zbl 0335.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.