I have two questions. Both are about finding any of the 3 largest among $n$ elements.

  1. How to show that $n-3$ comparisons suffice to find any of the $3$ largest among $n$ given numbers $(n \geq 4)$?

  2. How to show that $n-3$ comparisons are necessary to find any of the $3$ largest among $n$ given numbers $(n \geq 6)$?

My Idea: I have tried to solve 1. using a heap but could not derive any such bound.

The place where I found this question gave one hint which said to analyze the number of connected components in a comparison graph.

I shall appreciate if anyone can throw some light on a comparison graph.

  • $\begingroup$ The second one is only true if the set is not sorted. $\endgroup$
    – swegi
    Aug 20, 2012 at 20:13

1 Answer 1


I don't know what do you mean by comparison graph. However, here is my solution for question 1.

Suppose you have a list of $m$ elements, and you want to find the largest element. You can do this with $m-1$ comparisons.

Do you know how to proceed?

You can simply ignore the first two elements in your list. This gives you a new list $L'$ of $n'=n-2$ elements, You can determine the largest element of $L'$ with $n'-1=n-3$ comparisons. This element is one of the three largest.

  • $\begingroup$ I guess that he means decision tree when he says comparison graph. $\endgroup$
    – mrk
    Aug 20, 2012 at 9:30
  • 1
    $\begingroup$ @saadtaame: Yeah, but then I doesnt make sense to speak about connected components. Also decision trees are more a tool to show lower bounds. $\endgroup$
    – A.Schulz
    Aug 20, 2012 at 11:56
  • $\begingroup$ Thanks! It seems that I got the question wrong! I appreciate all the helps! $\endgroup$
    – aghost
    Aug 20, 2012 at 14:40
  • $\begingroup$ @AnirbanGhosh: I had a look on the original question you posted: Have you asked for the lower bound? I.e., that $n-3$ comparisons are always necessary? Also you should try to look up "decision tree" and see if it is the same than the "comparison graphs" you have mentioned. $\endgroup$
    – A.Schulz
    Aug 20, 2012 at 14:48
  • $\begingroup$ Actually I had two questions but somebody deleted the second question leaving the question incomplete! My second question was to show that at least $n-3$ comparisons are needed and this needs comparison graph as the problem suggested. $\endgroup$
    – aghost
    Aug 20, 2012 at 16:16

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.