# Find any of the 3 largest among $n$ elements

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.

• The second one is only true if the set is not sorted. – swegi Aug 20 '12 at 20:13

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.

• I guess that he means decision tree when he says comparison graph. – saadtaame Aug 20 '12 at 9:30
• @saadtaame: Yeah, but then I doesnt make sense to speak about connected components. Also decision trees are more a tool to show lower bounds. – A.Schulz Aug 20 '12 at 11:56
• Thanks! It seems that I got the question wrong! I appreciate all the helps! – aghost Aug 20 '12 at 14:40
• @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. – A.Schulz Aug 20 '12 at 14:48
• 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. – aghost Aug 20 '12 at 16:16