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_minloop 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 numberIf this is the optimal solution how can I prove the number of comparisons is n + lg n - 2.
Given n distinct numbers show that the second smallest element can be found in n + lg n - 2 comparisons in the worst case
algorithms;algorithm analysis
The algorithm with $n + \lceil \lg n \rceil -2$ comparisons uses tournament (lecture note from utdallas).To form a tournament tree: Compare $A[2i1]$ 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).