What is the number of comparisons required by an algorithm that repeatedly…
2021
What is the number of comparisons required by an algorithm that repeatedly finds and removes the current maximum element (i.e., partial selection sort) to find the fourth largest element in the given input list of 'n' elements?
Answer: D. 2(2n – 5) — The stem specifies that the algorithm repeatedly finds and removes the current maximum element (this is the well-known partial-selection-sort approach).…
- A.
2n – 3
- B.
2n – 4
- C.
2n – 5
- D.
2(2n – 5)
Attempted by 317 students.
Show answer & explanation
Correct answer: D
The stem specifies that the algorithm repeatedly finds and removes the current maximum element (this is the well-known partial-selection-sort approach). Finding the maximum of m elements by pairwise comparison always takes exactly m − 1 comparisons, so each successive pass over the shrinking list costs one comparison less than the pass before it.
Pass 1: scan all n elements and find the maximum (the 1st largest) — this takes n − 1 comparisons. Remove it from consideration.
Pass 2: scan the remaining n − 1 elements and find their maximum (the 2nd largest) — this takes n − 2 comparisons. Remove it.
Pass 3: scan the remaining n − 2 elements and find their maximum (the 3rd largest) — this takes n − 3 comparisons. Remove it.
Pass 4: scan the remaining n − 3 elements and find their maximum (the 4th largest) — this takes n − 4 comparisons.
Total comparisons = (n − 1) + (n − 2) + (n − 3) + (n − 4) = 4n − 10 = 2(2n − 5).
In general, finding the k-th largest this way needs (n − 1) + (n − 2) + … + (n − k) = k(2n − k − 1)/2 comparisons. Substituting k = 4 gives 4(2n − 5)/2 = 2(2n − 5), matching the total above. As a check with a small case, n = 5 and k = 4: the formula gives 4×5 − 10 = 10 comparisons, the same as counting the four passes directly (4 + 3 + 2 + 1 = 10).
So the number of comparisons required to find the 4th largest element is 2(2n − 5).