Skip to content

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.)

The smallest of $n$ numbers can be found with $n - 1$ comparisons by conducting a tournament as follows: Compare all the numbers in pairs. Only the smaller of each pair could possibly be the smallest of all $n$, so the problem has been reduced to that of finding the smallest of $\lceil n / 2 \rceil$ numbers. Compare those numbers in pairs, and so on, until there's just one number left, which is the answer.

To see that this algorithm does exactly $n - 1$ comparisons, notice that each number except the smallest loses exactly once. To show this more formally, draw a binary tree of the comparisons the algorithm does. The $n$ numbers are the leaves, and each number that came out smaller in a comparison is the parent of the two numbers that were compared. Each non-leaf node of the tree represents a comparison, and there are $n - 1$ internal nodes in an $n$-leaf full binary tree (see Exercise (B.5-3)), so exactly $n - 1$ comparisons are made.

In the search for the smallest number, the second smallest number must have come out smallest in every comparison made with it until it was eventually compared with the smallest. So the second smallest is among the elements that were compared with the smallest during the tournament. To find it, conduct another tournament (as above) to find the smallest of these numbers. At most $\lceil \lg n \rceil$ (the height of the tree of comparisons) elements were compared with the smallest, so finding the smallest of these takes $\lceil \lg n \rceil - 1$ comparisons in the worst case.

The total number of comparisons made in the two tournaments was

$$n - 1 + \lceil \lg n \rceil - 1 = n + \lceil \lg n \rceil - 2$$

in the worst case.

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.