No. of Comparisons to find maximum in $n$ Numbers Given $n$ numbers, we want to find the maximum. In order to find the maximum in a minimal amount of comparisons, we define a binary tree s.t. we compare $n'_1=\max(n_1,n_2)$, $n'_2=\max(n_3,n_4)$; $n''_1=\max(n'_1,n'_2)$ and so on.
How many maximum comparisons are needed to find the maximum of those $n$ numbers?
When drawing and trying out on paper, I came up with $n-1$ comparisons, but I'm not able to prove this. Any ideas? It's more or less easy to see if $n$ is divsible by 2.

It is fairly straight-forward to prove with induction that $k-1$ comparisons are enough to find the maximum of $n_1,\dotsc,n_k$.


*

*Clearly we need no comparisons to find the maximum of $n_1$.

*Consider now the numbers $n_1,\dotsc,n_k$ and assume that we can find the maximum of $k-1$ numbers with $k-2$ comparisons. Then we need only one last comparison because $\max(n_1,\dotsc,n_k) = \max(\max(n_1,\dotsc,n_{k-1}),n_k)$.
On the other hand, this is the best case possible, too: suppose that $n_1$ is the maximum of $n_1,\dotsc,n_k$. To decide that it actually is the maximum you need to compare it with each of $n_2,\dotsc,n_k$, i.e. you need $n-1$ comparisons.
