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

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.

• 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. – Yuval Filmus Nov 2 '14 at 16:43
• @YuvalFilmus Not yet. I will revisit the adversary argument to the second largest and try your idea. – hengxin Nov 3 '14 at 1:21
• @YuvalFilmus It is likely that the problem is still open. See my own answer below if you are interested. – hengxin Nov 4 '14 at 9:00

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!