Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS

Question

I was going through the text Introduction to Algorithms by Cormen et. al. where there was a discussion regarding the fact that finding the minimum of a set of $n$ (distinct) elements with $n-1$ comparisons is optimal as we cannot do better than it, which means that we need to show that running time of algorithm which finds the minimum of a set of $n$ elements is $\Omega(n)$.

This is what the text says to justify the lower bound.

We can obtain a lower bound of $n - 1$ comparisons for the problem of determining the minimum. Think of any algorithm that determines the minimum as a tournament among the elements. Each comparison is a match in the tournament in which the smaller of the two elements wins. Observing that every element except the winner must lose at least one match, we conclude that $n-1$ comparisons are necessary to determine the minimum.

Now I could make the thing out in my own way as:

What I have done is a top down comparison, but the authors by their words "Observing that every element except the winner must lose at least one match, we conclude that $n-1$ comparisons are necessary to determine the minimum." seems they are pointing to some bottom up approach which unfortunately I cannot make out.

How,

"That every element except the winner must lose at least one match" $\implies$ "$n-1$ comparisons are necessary to determine the minimum".

Answer 1

Every match has exactly one winner and one loser. If every element except the winner must lose at least one match, there must be at least $n-1$ matches, as otherwise there would be a match with two losers. So, at least $n-1$ matches are nessecary to determine a winner, i.e. $n-1$ comparisons are nessecary to determine the minimum.

---

The explanation given in the book is valid, but I personally prefer another approach. (which does require some elementary graph theory) Suppose you draw the graph with the elements as nodes and you draw an edge for each pair of elements that your algorithm compares. Note that it is impossible to know which of a pair of elements is smaller if there is no path between them in this graph. So, if we have determined the minimum, this graph must connected. Any connected graph on $n$ nodes has at least $n-1$ edges, so there must have been $n-1$ comparisons.