Abstrakt
V roce 1972 Pohl dokázal, že [3n/2]-2 porovnání stačí, ale v nejhorším případě je i nutných, při hledání minima i maxima n-prvkové uspořádané množiny. ordered set. Problém byl později zkoumán v kontextu Rényiho-Ulamových lhářských her, kde srovnávací orákulum může dát až k chybných odpovědí.
Pro velká k ukazuje Aignerův horní odhaz, že (k+O(\sqrt{k}))n porovnání stačí. Vylepšíme tento odhad pomocí algoritmu, kterému stačí (k+1+C)n+O(k^3) porovnání pro nějakou konstantu C.
Dolní odhady jsou známé ve tvaru (k+1+c_k)n-D, s konstantou D, kde c_0=0.5, c_1=23/32=0.71875, a c_k=\Omega(2^{-5k/4}) pro k jdoucí do nekonečna.