Second Largest with Minimum Comparisons
You have an array of $n$ distinct numbers. Design an algorithm that finds the second largest element using at most $n + \lceil \log_2 n \rceil - 2$ comparisons in the worst case.
1. Describe the algorithm and prove it achieves this bound.
2. Prove that no comparison-based algorithm can do better -- i.e., $n + \lceil \log_2 n \rceil - 2$ is a lower bound on the worst-case number of comparisons needed to find the second largest.
Open the full interactive solver, hints, and worked solution →