Minimum no. of comparisons required for finding 2nd minimum element

second smallest of n elements can be found with n + logn -2 in worst case..

Lets check out how?

See the pair-wise comparison below

1  2  3  4  5  6  7  8
 \/    \/    \/    \/
 1      3    5      7
   \  /        \  /
     1          5
        \   /
          1

1 is the smallest, it took n-1 = 7 comparisons. Now compare all the numbers which 1 was compared to (compare 2,3,5).

2  3   5
 \/   /
  2  /
   \/
   2

2 is the second smallest. It took lg(n)-1 = 2 comparisons.

So total is (n-1)+(logn-1) = n+logn-2 comparisons.