Prove that finding the maximum element is n-1

Question

How it can be proved that finding the maximum element in the n-element set requires at least n-1 comparisons?

I think it requires proof by induction.

Thank You in Advance.

Answer 1

All but the maximum element must lose a comparison or they might be the maximum. You need $n-1$ elements to lose a comparison, so you need $n-1$ comparisons.

Answer 2

If you did only n- 2 comparisons, there would be one member of the set that had not been compared to anything. That one member might well be the largest member of the set.

Answer 3

Suppose that it is true, that you need exactly $n-1$ comparisons, to find maximum of $n$-element set. Then, for a set $A$ of $n+1$ elements, select one of its elements, let it be $x$. Set $A - \{x\}$ has $n$ elements and therefore, to find its maximum, we need exactly $n-1$ comparisons. Now, $x$ can be greater that any of $A - \{x\}$, or it could be less or equal than any of them. This requires another comparison, and thus you need $n-1+1=n$ comparisons. This finishes the inductive step (base step needs to be verified too, but it's trivial).