0
$\begingroup$

I would like to prove that we need at least five comparisons to find median amoung five numbers.

And my proposition: Let's consider tree of comparisons. There are at least $5 \cdot {4\choose 2} = 30$ possiblities, so in our tree we have at least $30$ leaves. So what is minimal height of this tree when we have at least $30$ leaves. (height is number of comparisons).
So $$height \ge \log_2(30) > 4$$ Hence, $height \ge 5$.

Is it correct proof ?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ What are you counting exactly ? I don't understand what your 30 is. $\endgroup$ – François Aug 18 '15 at 15:08
  • $\begingroup$ Ok : 5 is the number of possible medians and ${4\choose 2}$ for the possible 2 larger elements once the median is selected. $\endgroup$ – François Aug 18 '15 at 15:27
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – Juho Aug 18 '15 at 19:00
  • $\begingroup$ It seems to me, that it is quite clear. My question is: Is it proof correct ? Answer is: Yeah, it is OK. $\endgroup$ – M.Swe Aug 18 '15 at 19:12
  • $\begingroup$ The question "is this proof correct" isn't interesting to anybody but you. The fact that you're not sure if your proof is correct or not points to an underlying uncertainty about something but we don't know what. If you turn your question into a question about that, it's much more likely to be useful to other people. It's that underlying question that's unclear. $\endgroup$ – David Richerby Aug 18 '15 at 20:33
3
$\begingroup$

Your proof is correct. But I don't think 5 comparisons is achievable. Here is the algorithm that finds the median in 6 comparisons.

  1. Sort the first two pairs. [ 2 comparisons]

  2. Order the pairs w.r.t. their respective larger element. [ 1 comparison]

    Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$. Now there are 3 elements less than $d$, hence $d$ can't be the median( i.e. $3^{rd}$element of the sorted array)

  3. WLOG say $c<e$ and $a<b$ (known already). Order the pairs w.r.t. their respective larger element. WLOG $a<b<e$ and $c<e$. Compare $c$ & $b$, greater one is the median. [ 3 comparisons - 1 for $c$ & $e$, 1 for ordering the pairs and 1 for $b$ & $c$ ]

Hence, total number of comparisons is equal to 6.

Idea taken from here .

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I also think that my proof is OK. $\endgroup$ – M.Swe Aug 18 '15 at 18:26
1
$\begingroup$

The proof is correct as you are calculating lower bound for median of 5 elements. But this is data dependent, so it is not number of compares algorithm needs to find median. This is one of instances.

Unless you are happy to know that there are such cases...

But to derive algorithm that works always you have to compute upper bound on this, to have algorithm (that always works). Minimal number independent of order of elements to find median of five elements is six.

Try it yourself. Take 5 numbers, let it be 1,2,3,4,5, permute them and draw trees of comparisons. In fact there are instances with five compares, but you will find instances of six, and this upper bound is interesting.

You might be also interested in this: http://www.cs.hut.fi/~cessu/selection/

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It is very curious now. I try to find median with 6 comparisons (algorithm). Nevertheless my task is: show that everty algorithm that find median in set (5 elements) do at least 5 comparisons in pesimistic case. $\endgroup$ – M.Swe Aug 18 '15 at 16:38
  • $\begingroup$ refer to my comment, your comment is useless $\endgroup$ – M.Swe Aug 18 '15 at 18:12

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