How many number of comparison are required in worst case to find out second…
2026
How many number of comparison are required in worst case to find out second smallest element of n elements list?
n + [log n]- 1
n + [log n]
[log n]
n +[log n] - 2
- A.
1
- B.
2
- C.
3
- D.
4
Attempted by 154 students.
Show answer & explanation
Correct answer: D
Finding the Second Smallest Element
To find the second smallest element in a list of n elements with the minimum number of comparisons in the worst case, we use a tournament method.
Step 1: Find the Smallest Element
We can find the smallest element by organizing the elements in a tournament structure. In each round, elements are paired and compared. The winner (smaller element) advances.
To find the minimum of n elements, we need exactly n - 1 comparisons. The smallest element will have defeated approximately log₂(n) other elements during the tournament.
Step 2: Find the Second Smallest Element
The second smallest element must be one of the elements that lost directly to the smallest element. Since the smallest element played at most ⌈log₂(n)⌉ matches, there are at most ⌈log₂(n)⌉ candidates for the second smallest.
We need to find the minimum among these candidates. This requires ⌈log₂(n)⌉ - 1 additional comparisons.
Total Comparisons
Total comparisons = (n - 1) + (⌈log₂(n)⌉ - 1) = n + ⌈log₂(n)⌉ - 2.
Thus, the number of comparisons required in the worst case is n + ⌈log n⌉ - 2.