CODEWITHSUNDEEP
algorithmcomparison
David
David

Reputation: 1159

minimum number of comparisons needed

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

Upvotes: 2

Views: 14608

Answers (4)

Franck Dernoncourt
Franck Dernoncourt

Reputation: 83387

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

Upvotes: 5

Rusty Rob
Rusty Rob

Reputation: 17203

for elements a,b,c,d

if a>b+c+d, then it only required one comparison to know that a is the biggest.

You do have to get lucky though.

Upvotes: -1

Karoly Horvath
Karoly Horvath

Reputation: 96286

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.

Upvotes: 3

Tomas
Tomas

Reputation: 59555

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.

Upvotes: 6

Related Questions