2
$\begingroup$

What is the lower bound for finding the third largest in a set of $n$ distinct elements?

For the case of finding the second largest, we have the tight lower bound of $n + \lceil \lg n \rceil -2$. The adversary argument can be found in this lecture, which also provides an optimal algorithm using the "Tournament Method".


Edit (04-04-2017): Removing the algorithm for finding the third largest element which turns out to be wrong.

$\endgroup$
  • 1
    $\begingroup$ Have you tried extending the adversary argument to the third largest? That's all we can do here, so it's better if you tried first. $\endgroup$ – Yuval Filmus Nov 2 '14 at 16:43
  • $\begingroup$ @YuvalFilmus Not yet. I will revisit the adversary argument to the second largest and try your idea. $\endgroup$ – hengxin Nov 3 '14 at 1:21
  • $\begingroup$ @YuvalFilmus It is likely that the problem is still open. See my own answer below if you are interested. $\endgroup$ – hengxin Nov 4 '14 at 9:00
2
$\begingroup$

Answer my own question:

At the end of "Lecture 28: Adversary Arguments" by Jeff Erickson, I found

A similar argument implies that at least $n - k + \lceil \lg {n \choose k-1} \rceil = \Omega \big( (n - k) + k \log (n / k) \big)$ comparisons are required to find the $k$-th largest element in an $n$-element set. This bound is tight up to constant factors for all $k \le n/2$; there is an algorithm that uses at most $O \big( n+k \log(n/k) \big)$ comparisons. Moreover, this lower bound is exactly tight when $k = 1$ or $k = 2$. In fact, these are the only values of $k \le n/2$ for which the exact complexity of the selection problem is known. Even the case $k = 3$ is still open!

Therefore, the current answer to the question is that it is still unknown.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.