## 7.8.2 Lower Bounds for Worst-Case Behavior To obtain a bound for the worst-case number of comparisons of keys, we need the following lemma. Lemma 7.2****The worst-case number of comparisons done by a decision tree is equal to its depth. Proof: Given some input, the number of comparisons done by a decision tree is the number of internal nodes on the path followed for that input. The number of internal nodes is the same as the length of the path. Therefore, the worstcase number of comparisons done by a decision tree is the length of the longest path to a leaf, which is the depth of the decision tree. **** By [Lemmas 7.1](LiB0064.html#722)and [7.2](LiB0064.html#723), we need only find a lower bound on the depth of a binary tree containing *n*! leaves to obtain our lower bound for the worst-case behavior. The required lower bound on depth is found by means of the following lemmas and theorems. Lemma 7.3****If *m* is the number of leaves in a binary tree and *d* is the depth, then  Proof: Using induction on *d*, we show first that  Induction base: A binary tree with depth 0 has one node that is both the root and the only leaf. Therefore, for such a tree, the number of leaves **m** equals 1, and  Induction hypothesis: Assume that, for any binary tree with depth *d*,  where *m* is the number of leaves. Induction step: We need to show that, for any binary tree with depth *d* + 1,  where *m*1 is the number of leaves. If we remove all the leaves from such a tree, we have a tree with depth *d* whose leaves are the parents of the leaves in our original tree. If *m* is the number of these parents, then, by the induction hypothesis,  Because each parent can have at most two children,  Combining these last two inequalities yields  which completes the induction proof. Taking the lg of both sides of Inequality [7.1](#ch07eqn01)yields  Because *d* is an integer, this implies  **** Theorem 7.2****Any deterministic algorithm that sorts *n* distinct keys only by comparisons of keys must in the worst case do at least  Proof: By [Lemma 7.1](LiB0062.html#709), to any such algorithm there corresponds a pruned, valid, binary decision tree containing *n*! leaves. By [Lemma 7.3](LiB0064.html#727), the depth of that tree is greater than or equal to \[lg (*n*!)\]. The theorem now follows, because [Lemma 7.2](#ch07ex10) says that any decision tree's worst-case number of comparisons is given by its depth. **** How does this bound compare with the worst-case performance of Mergesort—namely, *n* lg *n* – (*n* – 1)? [Lemma 7.4](LiB0064.html#729) enables us to compare the two. Lemma 7.4****For any positive integer *n*,  Proof:The proof requires knowledge of integral calculus. We have  **** Theorem 7.3****Any deterministic algorithm that sorts *n* distinct keys only by comparisons of keys must in the worst case do at least  Proof:The proof follows from [Theorem 7.2](LiB0064.html#727)and [Lemma 7.4](#ch07ex13). **** We see that Mergesort's worst-case performance of *n* lg *n* – (*n* – 1) is close to optimal. Next we show that this also holds for its average-case performance.