# 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. Commented Aug 20, 2012 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.
– mrk
Commented Aug 20, 2012 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. Commented Aug 20, 2012 at 11:56
• Thanks! It seems that I got the question wrong! I appreciate all the helps! Commented Aug 20, 2012 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. Commented Aug 20, 2012 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. Commented Aug 20, 2012 at 16:16