zbMATH — the first resource for mathematics

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 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 New York/Berlin
[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 Potomac, Md., · Zbl 0442.68022
[10] Knuth, D.E., Mathematical analysis of algorithms, () · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.