zbMATH — the first resource for mathematics

Lower bounds for finding the maximum and minimum elements with \(k\) lies. (English) Zbl 1305.68072
Summary: In this paper we deal with the problem of finding the smallest and the largest elements of a totally ordered set of size \(n\) using pairwise comparisons if \(k\) of the comparisons might be erroneous where \(k\) is a fixed constant. We prove that at least \((k+1.5)n+\Theta(k)\) comparisons are needed in the worst case thus disproving the conjecture that \((k+1+\varepsilon)n\) comparisons are enough.
68P10 Searching and sorting
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
search; lies
PDF BibTeX Cite