Chapter 4, Problem 42C

Explanation of Solution

Algorithm:

findMax(Array A, size n>0):

    max=A[0]

    for i in 1 to n (inclusive)

    if(A[i] > max)

        max=A[i]

    return max

Explanation:

The above algorithm uses a binary tree where every node keeps track of the maximum and minimum for the sub tree starting with that node.

Let us consider the three types as the following implementation to prove the maximum and minimum of “n” numbers. Type-1 contains less than “$3n/2$” comparisons, type-2 contains “$n/2$ ” nodes that have leaves as children, and type-3 contains less than “$n/2$” nodes where a least one of the children aren't leaves.

• First, start with the type 2 nodes, and compare the two leaves. This requires a maximum of “n/2” comparisons. If there are an odd number of type 1 nodes, the last node is promoted to type 2 and only it uses $\left(n-1\right)/2$ comparisons.
• Now there are “$n/2$ ” or “$\left(n-1\right)/2+1$ ”type 2 nodes.
• Let us take “m” be the number of nodes and keep pairing the nodes until only one node is left. In each iteration, it requires two comparisons while pairing two nodes