1
$\begingroup$

If we were to intuitively construct a lower bound for searching an element in a list $A$ containing $n$ integers, it would be in $\Omega(n)$.

But with the decision tree model, the number of leafs is $n$, so we conclude that the lower bound is $\Omega(\log{n})$.

This is the same as finding the maximum element in a list. Intuitively, it is in $\Omega(n)$, but with the decision tree model it is $\Omega(\log{n})$.

Can someone help me understand this discrepancy ?

Thank you in advance.

$\endgroup$

1 Answer 1

4
$\begingroup$

The bound you're describing is that the depth of the decision tree is at least the logarithm of the number of distinct answers. This bound always holds, but is not always tight. In the case of searching an element in a list, it is tight when the list is sorted, and not tight if we don't assume anything on the list. The reason for this discrepancy is that the bound doesn't distinguish between the two cases — it is too general.

I challenge you to come up with another argument showing that the depth of a decision tree for finding an element in a list is at least $n$ (or even $n+1$, depending on how depth is defined).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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