1
$\begingroup$

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 ??

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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