AMU 2026 — Computer PYQ
AMU | Computer | 2026Minimum number of comparisons required to compute the largest and second largest element in an array is :
Preparing for Excellence...
Minimum number of comparisons required to compute the largest and second largest element in an array is :
n⌈log2n⌉−2
n+⌈log2n⌉−2
log2n
n−⌈log2n+1⌉
n+⌈log2n⌉−2
To find both the largest and second largest elements using the minimum possible number of comparisons, we use a specialized approach known as the Tournament Method (or Adversary/Knockout Tournament).
Step 1: Finding the Largest Element
Imagine a knockout tournament setup where elements are paired up and compared in rounds.
In a tournament of n players (elements), it takes exactly n−1 matches (comparisons) to determine a single absolute winner (the largest element).
Comparisons needed for the largest element:
C1=n−1
Step 2: Finding the Second Largest Element
The second-largest element can only be an element that was directly beaten by the absolute largest element during the tournament matches.
In a perfectly balanced binary tournament tree, the maximum number of rounds an element plays to win the tournament is equal to the height of the tree, which is ⌈log2n⌉.
Therefore, the winner (largest element) has directly defeated exactly ⌈log2n⌉ elements.
To find the second-largest element among these candidates, we must look only at these defeated elements and find the maximum among them.
Finding the maximum among k elements requires k−1 comparisons. Substituting k=⌈log2n⌉:
C2=⌈log2n⌉−1
Step 3: Calculating Total Minimum Comparisons
Summing up the comparisons from both steps:
Total Comparisons=C1+C2
Total Comparisons=(n−1)+(⌈log2n⌉−1)
Total Comparisons=n+⌈log2n⌉−2
The minimum formula matching this optimal algorithmic bounds structure is n+⌈log2n⌉−2, making choice (b) the correct option.
To find both the largest and second largest elements using the minimum possible number of comparisons, we use a specialized approach known as the Tournament Method (or Adversary/Knockout Tournament).
Step 1: Finding the Largest Element
Imagine a knockout tournament setup where elements are paired up and compared in rounds.
In a tournament of n players (elements), it takes exactly n−1 matches (comparisons) to determine a single absolute winner (the largest element).
Comparisons needed for the largest element:
C1=n−1
Step 2: Finding the Second Largest Element
The second-largest element can only be an element that was directly beaten by the absolute largest element during the tournament matches.
In a perfectly balanced binary tournament tree, the maximum number of rounds an element plays to win the tournament is equal to the height of the tree, which is ⌈log2n⌉.
Therefore, the winner (largest element) has directly defeated exactly ⌈log2n⌉ elements.
To find the second-largest element among these candidates, we must look only at these defeated elements and find the maximum among them.
Finding the maximum among k elements requires k−1 comparisons. Substituting k=⌈log2n⌉:
C2=⌈log2n⌉−1
Step 3: Calculating Total Minimum Comparisons
Summing up the comparisons from both steps:
Total Comparisons=C1+C2
Total Comparisons=(n−1)+(⌈log2n⌉−1)
Total Comparisons=n+⌈log2n⌉−2
The minimum formula matching this optimal algorithmic bounds structure is n+⌈log2n⌉−2, making choice (b) the correct option.