9.1 Minimum and maximum

9.1-1

We know that we need n - 1 comparisions to find the smallest element. Let's define an algorithm to find the smallest element:

FIND-THE-SMALLEST(A, low, high)

mid = (low + high) / 2
left-min = FIND-THE-SMALLEST(A, low, mid)
right-min = FIND-THE-SMALLEST(A, mid + 1, high)
return min(left-min, right-min)

The root node of the recursive tree has two children, one of them is the smallest element, let's assume the left child is the smallest element and let k denote the right child, then in order to find the second smallest element, we can traverse through the left branch, we let the smaller value of left and right children be the value of each node.

When we are traversing, we compare the current second smallest element with the child with larger value (because the smaller one is the smallest element), if it's smaller than the second smallest element, we update the second smaller element.

Because we only compare the smaller element with k in each node, so we don't need to traverse all branches in left branch. Since the height of recursive tree is $\lceil \lg{n} \rceil$, thus we need $\lceil \lg{n} \rceil - 1$ comparisions. So we need $n - 1 + \lceil \lg{n} \rceil - 1 = n + \lceil \lg{n} \rceil - 2$ comparisions.

9.1-2

The analysis is similar like the analysis in the book. When n is even, we need $\frac{3n}{2} - 2$ comparisions, which is also $\lceil \frac{3n}{2} \rceil - 2$. When n is odd, we need $3\lfloor \frac{n}{2} \rfloor$ comparisions. And:

$$ \begin{eqnarray} 3\lfloor \frac{n}{2} \rfloor &=& 3\lceil \frac{n - 2 + 1}{2} \rceil \\ &=& 3\lceil \frac{n - 1}{2} \rceil \\ &=& \lceil \frac{3(n - 1)}{2} \rceil & (n \text{ is odd}) \\ &=& \lceil \frac{3n}{2} - \frac{3}{2} \rceil \\ &=& \lceil (\frac{3n}{2} + \frac{1}{2}) - (\frac{3}{2} + \frac{1}{2}) \rceil \\ &=& \lceil \frac{3n}{2} + \frac{1}{2} \rceil - \lceil \frac{3}{2} + \frac{1}{2} \rceil \\ &=& \lceil \frac{3n}{2} \rceil - 2 \end{eqnarray} $$

So when n is odd, it also needs $\lceil \frac{3n}{2} \rceil - 2$ comparisions.