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 conjecture relating minimax and minimean complexity norms. (English). Aplikace matematiky, vol. 24 (1979), issue 5, pp. 321-325
MSC: 68C25, 68Q25, 68W99 | MR 0547036 | Zbl 0434.68029 | DOI: 10.21136/AM.1979.103813
Keywords:
minimax and minimean complexity; optimal algorithm; uniform complexity
Summary:
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.
References:
[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