Given n distinct numbers show that the second smallest element can be found in n + lg n - 2 comparisons in the worst case
The algorithm with $n + \lceil \lg n \rceil -2$ comparisons uses "tournament" (lecture note from utdallas).


To form a tournament tree: Compare $A[2i−1]$ with $A[2i]$ for $i = 1$
to $n$. We compare the "winners" in pairs and so on.
Collect all the keys that directly lost to the maximum and compute their maximum. That is, the second largest key.


The time complexity is $(n-1) + (\lceil \lg n \rceil - 1) = n + \lceil \lg n \rceil -2$.



Actually, the lower bound for "finding the second largest/smallest element" is $n + \lceil \lg n \rceil -2$, which can be proved by adversary argument (at the end of the lecture above).