# Lower bound on the number of comparisons needed for finding the two largest elements

Given a sequence of ݊different elements, there is an algorithm that finds the maximum element, and the 2nd largest element, using n +log_2(n) - 2 comparisons. Prove that any algorithm will have to perform at least n +log_2(n) - 2 comparisons in order to find both elements.

What I've done: I tried to compare it to a tennis tournament(sort of a binary tree that compare pairs of competitors in which each game has a winner and a loser - each winner goes up to the next level in the tree). It takes n-1 comparisons and every element is involved in a comparison log n times at most.

The biggest element will be the winner in the tournament. the second biggest element will have to face the winner so he's one of the log n elements the the winner competed against which means logn -1 comparisons. If I sum it all I get what I need to prove.

I got this note from the teacher: the proof is not correct because you assume the algorithm uses a tournament you have to prove any algorithm has an input for which the second largest element is in a group of size logn.

Can someone tell me how the proof should have looked like? I'm really struggling with it. Please be detailed as possible

## migrated from stackoverflow.comApr 4 '17 at 15:42

This question came from our site for professional and enthusiast programmers.

• To be honest you exactly describe an algorithm doing it in the minimum amount of comparisons. Maybe it's not formal enough because you don't show why there cannot be fewer comparisons. Prove by contradiction and that stuff... – maraca Mar 26 '17 at 0:57
• See here for some useful references. – Raphael Apr 4 '17 at 18:57