9.1-1

9.1-1 Show that the second smallest of n elements can be found with n + lg n - 2 comparisons in the worst case. (Hint: Also find the smallest element.)

To find the smallest number n-1 comparisons are made. To find the smallest conduct a tournament every number looses exactly once except the smallest. If we draw a binary tree there are n leaves and n-1 non leaf nodes. Every non leaf node represents a comparison hence we need n-1 comparisons. To find the smallest number the second smallest number must have come out smallest in every comparison except with the smallest number. To find the second smallest number conduct another tournament to compares all these numbers. At most log n elements(the height of binary tree) were compared with smallest number.So finding the smallest of these will take $\lceil log n \rceil - 1$ the total number of comparisions are $n- 1+ \lceil log n \rceil - 1$