1
$\begingroup$

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:

TOP-DOWN

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".

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The graph explanation is great!! Thanks for the help. $\endgroup$ – Abhishek Ghosh Jun 23 at 8:44
  • $\begingroup$ And for the text explanation, I got it, in each comparison we are rejecting $1$ element from our list. So to select the winner we need to remove $n-1$ elements from the list so $n-1$ comparisons . Less than that would mean in each comparison we are rejecting two elements. $\endgroup$ – Abhishek Ghosh Jun 23 at 9:01
  • $\begingroup$ I would not say that less than $n-1$ comparisons means that in each comparison we are rejecting two elements; rather, if I perform less than $n-1$ comparisons, the algorithm can not be always correct. $\endgroup$ – Massimo Cafaro Jun 23 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.