About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

First Page Preview
Růžička, Peter ; Wiedermann, Juraj
On the lower bound for minimum comparison selection. (English). Aplikace matematiky, vol. 23 (1978), issue 1, pp. 1-8
MSC: 68C25, 68E05, 68Q25, 68R99 | MR 0480156 | Zbl 0418.68061 | DOI: 10.21136/AM.1978.103726
Keywords:
minimum comparison; selection algorithm; worst-case complexity; lower bound; adversary strategy; selection problem
References:
[1] M. Blum R. W. Floyd V. Pratt R. Rivest R. Tarjan: Time bounds for selection. JCSS 7 (Aug. 1973), 448-461. MR 0329916
[2] L. Hyafil: Bounds for selection. IRIA Rapport de Recherche n° 77. 1974. MR 0464673
[3] D. E. Knuth: The art of computer programming. Volume 3. Sorting and Searching. Addison-Wesley publishing company. 1973. MR 0445948
[4] V. Pratt F. F. Yao: On lower bounds for computing the i-th largest elements. Proceedings of the Fourteenth Symposium on Switching and Automata Theory. 1973. MR 0468319
[5] A. Schönhage M. Paterson N. Pippenger: Finding the median. Theory of Computation Report. The University of Warwick. 1975. MR 0428794
Partner of
EuDML logo