What is the number of comparisons required by an algorithm for finding the…
2022
What is the number of comparisons required by an algorithm for finding the fourth largest element in the given input list of ‘n’ elements?
- A.
2n – 3
- B.
2n – 4
- C.
2n – 5
- D.
2(2n – 5)
Attempted by 180 students.
Show answer & explanation
Correct answer: C
To find the 4th largest element , treat it as selecting k = 4 largest. For the k-th largest , using selection by pairwise comparison: Comparisons=2n−k−1 Put k=4: 2n−4−1=2n−5 ✔ Answer = 2n – 5