# Decision tree and information-theoretic lower bound

Consider the following problem :

Consider the problem of finding the median of a three-element set {a, b, c}.
a. What is the information-theoretic lower bound for comparison-based
algorithms solving this problem?
b. Draw a decision tree for an algorithm solving this problem.


The answer of this problem is shown below :

My problem is with number a. According to my understanding the information theoretic lower bound = ceil (log2(2!)) , so in this question it should be equal to ceil (log2(6)) =3 because here we have 6 leaves not 3 ?

No. The outcome is the median, not the sorted list. Thus, there are only 3 possible outcomes, not 3! outcomes. The information-theoretic lower bound says that if there are N possible outcomes, then it takes at least $$\lceil \lg N \rceil$$ comparisons. (Proof: given $$k$$ comparisons, you can only produce $$2^k$$ different outcomes.) Here $$N=3$$.

• I am confused between it and the lower bound which is ceil(log2(2!)) please clarify this difference? – John adams Apr 15 '20 at 3:01