TADM2E 4.15

a) First find the smallest element via n-1 comparisons, then remove the smallest from the array and call HEAPIFY (log n-1) and lastly extract-min. so totally n + log n -2.

b) The tournament algorithm is the best algorithm to find the 2nd largest element. In tournament algo we need to pair up 2 elements and then find the winner. then again do the same with the winners. Like a knockout football game. The second largest number can be any one in the list of numbers which lost to the winner. Check the winner in the losers group (lost to the best element). This can be done in n+log(n) time complexity.

Solution B for a): Compare the first 3 elements and get rid of the smallest. Repeat this ( n - 2 ) times until we are done with all elements. Since it only takes at most 2 comparison to find the smallest element out of three, the total would be 2(n-2) = 2n-4 < 2n-3. This methods also applies to b).