algorithms - Lower bound for finding second largest element - Mathematics Stack Exchange

The optimal algorithm uses n+log n-2 comparisons. Think of elements as competitors, and a tournament is going to rank them.

First find the maximum using a "tennis tournament" structure: first compare the n elements in pairs, then compare the n/2 "winners" in pairs, and so on. (Unpaired elements get a bye to the next round.) Since every element except the winner loses exactly once, this takes n−1 comparisons. But now note that the second largest element must be one which lost to the winner, as it couldn't have been defeated by any other element. So you need to find the maximum among all the (up to) ⌈lgn⌉ elements that were defeated by the winner, and finding this maximum can be done in ⌈lgn⌉−1.
From https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf
Read full article from algorithms - Lower bound for finding second largest element - Mathematics Stack Exchange