Previous |  Up |  Next


minimax and minimean complexity; optimal algorithm; uniform complexity
Using counterexample it has been shown that an algorithm which is minimax optimal and over all minimax optimal algorithms is minimean optimal and has a uniform behaviour need not to be minimean optimal.
[1] D. E. Knuth: The Art of Computer Programming. Volume 3. Sorting and Searching. Addison-Wesley. 1973. MR 0445948
[2] I. Pohl: Minimean Optimality in Sorting Algorithms. Proceedings of 16th Annual Symposium on Foundations of Computer Science. 1975, 71 - 74. MR 0433968
[3] I. Pohl: On Selection over Six Elements and a Conjecture Relating Two Complexity Norms. Vrije Universiteit. Wiskundik Seminarium. Amsterdam. March 1975.
Partner of
EuDML logo