Second Largest with Minimum Comparisons
Problem statement
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.
- Describe the algorithm and prove it achieves this bound.
- 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.
Show hint
Which elements are the only possible candidates for the runner-up once you know who beat whom?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.