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.
 D. E. Knuth: The Art of Computer Programming. Volume 3. Sorting and Searching
. Addison-Wesley. 1973. MR 0445948
 I. Pohl: Minimean Optimality in Sorting Algorithms
. Proceedings of 16th Annual Symposium on Foundations of Computer Science. 1975, 71 - 74. MR 0433968
 I. Pohl: On Selection over Six Elements and a Conjecture Relating Two Complexity Norms. Vrije Universiteit. Wiskundik Seminarium. Amsterdam. March 1975.