Consider finding both the largest and second largest elements from a set of $n$ elements by means of comparisons.
Prove that $n+\lceil \log n \rceil -2$ comparisons are necessary and sufficient.
Could you give me some hints how I could do that ??
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Since I cannot post a comment I make this into an answer.
This answer provides the desired lower bound for finding only the second largest element and provides an algorithm which finds both the largest and the second largest element in desired number of comparisons. So it solves your question.
$\begingroup$
$\endgroup$
If you run an elimination tournament among the elements, you can find the largest in $n-1$ comparisons. The second largest could be any one of the elements that lost to he final winner. How many is that?
answered Dec 5, 2014 at 19:07