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.
What is the lower bound for finding the third largest in a set of $n$ distinct elements?
complexity theory;reference request;time complexity;lower bounds;search problem
Answer my own question:At the end of Lecture 28: Adversary Arguments by Jeff Erickson, I foundA 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.