minimum number of comparisons needed

Question

what is the minimum number of comparisons needed to find the largest element from 4 distinct elements? I know for 5 distinct numbers it is 6, floor(5/2) * 3; this is from clrs book. but I know there is no one general formula for finding this, or is there?

edit clarification

these 4 elements could be in any different order(for all permutations of these 4 elements) im not interested in a counting technique to keep track of the largest element as you traverse the elements, but comparisons like > or <.

Solution 1

for 4 elements the min. number of comparisons is 3.

In general, to find largest of N elements you need N-1 comparisons. This gives you 4 for 5 numbers, not 6.

Proof:

1. there is always a solution with N-1 comparisons: just compare first two and then select the larger and compare with next one, select the larger and compare with next one etc....

2. there cannot be shorter solution because this solution would not compare all the elements.

QED.

Solution 2

I know it does not answer the original question, but I enjoyed reading this not-so-intuitive post on the minimum number of comparisons needed to find the smallest AND the largest number from an unsorted array (with proof).

Solution 3

Think of it as a competition. By comparing two elements you have a looser and a winner.

So if you have n elements and need 1 final winner you need n-1 comparisons to rule out the other ones.