The second smallest of n elements can be found with ____________ comparisons in the worst case.

1. An − 1
2. Blog n
3. Cn + ⌈log n⌉ − 2
4. D3n/2

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. n + ⌈log n⌉ − 2

Explanation

A tournament finds the minimum in n − 1 comparisons; the second smallest lost directly to the minimum, among ⌈log n⌉ candidates, needing ⌈log n⌉ − 1 more.