The second smallest of š¯‘› elements can be found with ____ comparisons in theā€¦
2018
The second smallest ofĀ š¯‘›Ā elements can be found with ____ comparisons in the worst case.
- A.
\(n-1\) - B.
\(\lg \: n\) - C.
\(n + ceil(\lg \: n)-2\) - D.
\(\frac{3n}{2}\)
Attempted by 54 students.
Show answer & explanation
Correct answer: C
Answer: n + ceil(log2 n) - 2 comparisons
Explanation:
Run a single-elimination tournament to find the minimum. Each comparison eliminates one element, so this requires n - 1 comparisons. While running the tournament, record for the eventual overall minimum each element it directly beat.
In the tournament the overall minimum participates in at most ceil(log2 n) matches, so it directly beats at most ceil(log2 n) elements.
The second smallest must be the smallest among those elements that lost directly to the overall minimum. Finding the minimum among k elements takes k - 1 comparisons, so this costs at most ceil(log2 n) - 1 additional comparisons.
Total comparisons in the worst case = (n - 1) + (ceil(log2 n) - 1) = n + ceil(log2 n) - 2.
A video solution is available for this question ā€” log in and enroll to watch it.