Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

Question

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.

I want to prove that finding the maximum in $A$ (that is, outputting the index at which the maximum is found in $A$) takes at least $\lceil n/2 \rceil$ comparison by assuming that there exists an algorithm that can find the maximum in at most $\lceil n/2 \rceil -1$ comparisons.

I tried assuming that there is such an algorithm, then took as an initial input some particular array $A$ (just a basic one, namely $1,2,3,\cdots,n$) and then tried changing it somehow so that the the algorithm follows the same path in the decision tree, but outputs the wrong index.

I do not know how I should change the array such that we have the same path in the decision tree. Also, maybe this is not the best array to try such a thing.

I thank you in advance!

Answer 1

In fact, at least $n-1$ comparisons are needed. Indeed, consider the graph on the vertex set $A$ whose edges correspond to pairs of elements which were compared. If less than $n-1$ comparisons were made, then the graph will have at least two connected components, and in particular, we can partition it into two non-empty sets $A_1,A_2$ with no edges between them. It is consistent that all elements in $A_1$ are smaller than all elements in $A_2$, in which case the maximum is in $A_2$. Similarly, the maximum could be in $A_1$. The algorithm cannot tell which is which, hence will be wrong on at least one of these scenarios.

---

The exercise was probably aiming at the following simpler argument: if less than $\lceil n/2 \rceil$ comparisons are made, then there is at least one element which is not compared at all. Hence for all we know, it could be the maximum, or the minimum (if these are different!); indeed, it could be at any position at all. This argument works as long as $n > 1$.