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$.