What is the minimum number of pairwise comparisons needed for identifying the largest, IInd largest & IIIrd largest elements out of 128 objects?
-
UP 0 DOWN 0 0 2
2 Answers
1127 + 6 + 6 is the answer!
127 = (64+32+16+8+4+2+1) comparisons at 1st stage.
The IInd stage for determining IInd largest element will consist of 6 comparisons & tha same number of comparisons will be needed for the IIIRd largest element.
Now, can u give an explanation vy is this so??
1no it is not!
You made a mistake in judging the result!!
It is actually equal to 26+25+24+23+22+22+21+20=64+32+16+8+4+2+1.
This is because in the first round we will be comparing the 128 objects pairwise....which means (1, 2), (3, 4), (5, 6),......, (127, 128) => 64 comparispns.
Now, the 64 winners of the first round, will compete among themselves in 32 comparisons & this will continue until we find the HEAVIEST OBJECT!!!
Hence, 64 + 32 + 16 + 8 + 4 + 2 + 1= 127 are the minimum PAIRWISE comparisons are needed to find out the HEAVIEST object of 128 objects.