[Algo] Exercise 9.1

Exercise 9.1-1
Show that the second smallest of n elements can be found with $n + \lceil\lg n\rceil - 2$ comparisons in the worst case. (Hint: Also find the smallest element.)
solution:
Imagine that each comparison is a match, the minimum is the final champion. As we have already known, it requires at least $n - 1$ comparisons to determine who is the winner. The second place must have been compared to the minimum and defeated. To find who is the second smallest, we can trace each match the minimum played. Gather all these defeated items and pick the smallest among them, it is the very second smallest. The minimum must play $\lceil \lg n\rceil$ games, so there are $\lceil \lg n\rceil$ candidates. To find the second smallest, we require another $\lceil \lg n\rceil - 1$ games. Therefore, there are $n - 1 + \lceil \lg n\rceil - 1 = n + \lceil \lg n\rceil - 2$ comparisons.


Exercise 9.1-2
Show that $\lceil 3n/2 \rceil - 2$ comparisons are necessary in the worst case to find both the maximum and minimum of n numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts.)
solution:
Initially, there are n potential items of maximum candidates and minimum candidates. If $a_i$ and $a_j$ are simultaneous in the candidate set of maximum and minimum respectively, after $a_i$ compares to $a_j$ the cardinality of candidate set of maximum and minimum will decrease by 1. If $a_i$ and $a_j$ are in the candidate set of maximum or minimum, after $a_i$ compares to $a_j$ the cardinality of the set will decrease by 1.
(1) when n is even:
After $n/2$ comparisons, the candidate set of maximum and minimum will remain $n/2$ candidates. Next, it requires $n/2 - 1$ comparisons to determine the maximum and another $n/2 - 1$ comparisons to determine the minimum. Total comparisons needed is $3n/2 - 2 = \lceil 3n/2 \rceil -2$.
(2) when n is odd:
After $(n-1)/2$ comparisons, the candidate set of maximum and minimum will remain $(n+1)/2$ candidates. Next, it requires at most $(n+1)/2 - 1$ comparisons to determine the maximum and another at most $(n+1)/2 - 1$ comparisons to determine the minimum. Total comparisons needed is $3n/2 - 3/2 = \lceil 3n/2 \rceil -2$.