0
$\begingroup$

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 : enter image description here

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 ?

$\endgroup$
1
$\begingroup$

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

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

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.