Given n distinct numbers show that the second smallest element can be found in n + lg n - 2 comparisons in the worst case This is a question from Introduction to Algorithms by CLRS (Exercise 9-1-1).

The approach I thought of is 


compare the first two numbers, assign the lower number min and the bigger one to next_min
loop through numbers 3 - n,
if the number is lower than min, set min to that number.
else if the number if lower than next_min set next_min to that number


If this is the optimal solution how can I prove the number of comparisons is n + lg n - 2.
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).