# 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.
##### MSC:
 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