We are given a collection of \(n\) values. Common sense (and also CLRS section 9.1) says that to find the maximum we need to make \(n-1\) comparisons. The challenge is to find the maximum using only \(O(\log n)\) comparisons.
To make the problem concrete, let the values be integers in the range \({1,...,M}\) for some constant \(M\). We’re only counting comparisons, so treat any arithmetic operations as zero-cost.
Recall the complexity lower-bound for sorting a list of \(n\) items (Algorithms 1 section 2.5): any sorting algorithm is effectively a decision tree, identifying one one of \(n!\) possible permuations, so we need \(\Omega(\log n!)=\Omega(n\log n)\) binary comparisons to discriminate between them. If we make sure the decision tree is balanced, we can achieve \(\Theta(n\log n)\).
Apply this thinking to the problem of finding the maximum of \(n\) items. We have to identify one of \(n\) possible answers, which needs \(\Omega(\log n)\) binary comparisons. Why shouldn’t this be achievable?