How would you use a decision tree to prove that searching a sorted list of n elements has the lower bound Omega(log n) with the comparison based model?
If you have to use a decision tree...
For a given length n, the behaviour of a comparison-based algorithm can be represented as a decision tree wherein each leaf is the result you get after the sequence of comparisons and results represented by the path to that leaf.
You have prove that, in a decision tree with n leaves and a branching factor of 3, the longest path to a leaf must have at least ceil(log_3(n)) internal nodes.
You would prove this inductively, demonstrating that it is so for n in {1,2,3}, and that implies it is true for all greater n, because if a node's subtree has n leaves, then one of its children needs to have at least n/3 leaves.