# prove that minimal number of comparisons to find median among five elements is 5 [closed]

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 ?

• What are you counting exactly ? I don't understand what your 30 is. Aug 18, 2015 at 15:08
• Ok : 5 is the number of possible medians and ${4\choose 2}$ for the possible 2 larger elements once the median is selected. Aug 18, 2015 at 15:27
– Juho
Aug 18, 2015 at 19:00
• It seems to me, that it is quite clear. My question is: Is it proof correct ? Answer is: Yeah, it is OK. Aug 18, 2015 at 19:12
• 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. Aug 18, 2015 at 20:33

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 .

• I also think that my proof is OK. Aug 18, 2015 at 18:26

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/

• 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. Aug 18, 2015 at 16:38
• refer to my comment, your comment is useless Aug 18, 2015 at 18:12