Previous |  Up |  Next


minimum comparison; selection algorithm; worst-case complexity; lower bound; adversary strategy; selection problem
[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