9.1 Minimum and maximum

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. ($\textit{Hint:}$ Also find the smallest element.)

We can compare the elements in a tournament fashion - we split them into pairs, compare each pair and then proceed to compare the winners in the same fashion. We need to keep track of each "match" the potential winners have participated in.

We select a winner in $n − 1$ matches. At this point, we know that the second smallest element is one of the lgn elements that lost to the smallest - each of them is smaller than the ones it has been compared to, prior to losing. In another $\lceil \lg n \rceil − 1$ comparisons we can find the smallest element out of those.

9.1-2 $\star$

Prove the lower bound of $\lceil 3n / 2 \rceil - 2$ comparisons in the worst case to find both the maximum and minimum of $n$ numbers. ($\textit{Hint:}$ Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts.)

If $n$ is odd, there are

$$ \begin{aligned} 1 + \frac{3(n-3)}{2} + 2 & = \frac{3n}{2} - \frac{3}{2} \\ & = (\bigg\lceil \frac{3n}{2} \bigg\rceil - \frac{1}{2}) - \frac{3}{2} \\ & = \bigg\lceil \frac{3n}{2} \bigg\rceil - 2 \end{aligned} $$

comparisons.

If $n$ is even, there are

$$ \begin{aligned} 1 + \frac{3(n - 2)}{2} & = \frac{3n}{2} - 2 \\ & = \bigg\lceil \frac{3n}{2} \bigg\rceil - 2 \end{aligned} $$

comparisons.