6
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I guess that he means decision tree when he says comparison graph. $\endgroup$ – saadtaame Aug 20 '12 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 '12 at 11:56
  • $\begingroup$ Thanks! It seems that I got the question wrong! I appreciate all the helps! $\endgroup$ – aghost Aug 20 '12 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 '12 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 '12 at 16:16

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.