Chapter 9.1

First we build a binary tree to find the smallest element, we split the n elements to \(\lceil n / 2 \rceil\) pairs and put them in the bottom of the tree, then we compare the elements of each pair and make the smaller one to be the parent node of the pair, we keep doing the reduction until we reach the top of the tree, then we find the smallest element, the number of comparisons is \(n - 1\).

Then we consider the second smallest element, we have already compared the second smallest element to the smallest element in the first step, we trace the path of the smallest element in the tree, the smallest element between those have compared to the smallest element, is the second smallest element, and the number of comparisons we need in this step is at most \(\lceil \lg n \rceil - 1\).

The total number of comparisons is at most \(n + \lceil \lg n \rceil - 2\).

(implementation)

Let \(S_{max}\) be the set of numbers which are potentially the maximum, and \(S_{min}\) be the set of numbers which are potentially the minimum. At the beginning, both \(S_{max}\) and \(S_{min}\) contain all \(n\) numbers.

After each comparison of two number \(a\) and \(b\), if \(a \geq b\), we can remove \(a\) from \(S_{min}\) if \(a \in S_{min}\), and remove \(b\) from \(S_{max}\) if \(b \in S_{max}\).

In the best case, we first take \(\lfloor n / 2 \rfloor\) comparisons, to reduce the sizes of \(S_{max}\) and \(S_{min}\) to \(\lfloor n / 2 \rfloor\) and \(\lceil n / 2 \rceil\), then we take \(\lfloor n / 2 \rfloor - 1 + \lceil n / 2 \rceil - 1 = n / 2 - 2\) comparisons to get the maximum and minimum, by comparing the numbers in \(S_{max}\) and comparing the numbers in \(S_{min}\), the total number of comparisons is \(\lfloor n/2 \rfloor + n/2 - 2 = \lfloor 3n/2 \rfloor - 2\).