2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$
    – maraca
    Mar 26, 2017 at 0:57
  • $\begingroup$ See here for some useful references. $\endgroup$
    – Raphael
    Apr 4, 2017 at 18:57

1 Answer 1

4
$\begingroup$

With impossibility proofs, you don’t control the algorithm; you control the input. For this particular impossibility proof, the input is the outcome of the comparisons that the algorithm performs. Here’s one possible adversary strategy.

This adversary never claims that elements in distinct positions are equal. At each point in the algorithm’s execution, there are two classes of elements: candidates, which are the elements that have not compared less than another element; and non-candidates, which are the remaining elements. Candidates always compare greater than non-candidates. Non-candidates compare in an arbitrary consistent way. Comparisons between candidates can be resolved arbitrarily (prove this); the adversary declares the candidate involved in more previous comparisons of this sort (“knockout” comparisons) to be greater.

At the end of the execution, there can be only one candidate; otherwise, the algorithm can’t know which of the candidates is the maximum (prove this). The only way to reduce the number of candidates is a knockout comparison, which reduces the number of candidates by one. This implies that there are n - 1 knockout comparisons, forming a tournament tree of some shape. We observe that, for each node of the tree, when an element secures its place there, it has participated in a number of knockout comparisons equal to the height of that node. The root has height at least lg n, so it takes lg n - 1 comparisons to determine which of the lg n elements compared less than the maximum only (otherwise, the second maximum isn’t known). None of these comparisons are knockouts, so the total is at least n + lg n - 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.