9.8.2 Result 2: Lower Bound on Average Case Complexity

We shall show that in any decision tree with K leaves, the average depth of a leaf is at least log K

We shall show the result for any binary tree with K leaves.

Suppose the result is not true. Suppose T is the counterexample with the fewest nodes.

T cannot be a single node because log 1 = 0. Let T have k leaves. T can only be of the following two forms. Now see Figure 9.6.
 
 

Figure 9.6: Two possibilities for a counterexample with fewest nodes

Suppose T is of the from Tree 1. The tree rooted at n₁, has fewer nodes than T but the same number of leaves and the hence an even smaller counterexample than T. Thus T cannot be of Tree 1 form.

Suppose T is of the form of Trees 2. The trees T₁ and T₂ rooted at n₁ and n₂ are smaller than T and therefore the

$$\geq$$ Average depth of  T₁ logk₁

$$\geq$$ Average depth of  T₂ logk₂

Thus the average depth of T

$$\geq {\frac{k_1}{k_1 + k_2}} {\frac{k_2}{k_1 + k_2}}$$

$${\frac{k_1}{k}} {\frac{k_2}{k}} \left(\vphantom{\frac{k_1}{k} +\frac{k_2}{k} }\right. {\frac{k_1}{k}} {\frac{k_2}{k}} \left.\vphantom{\frac{k_1}{k} +\frac{k_2}{k} }\right)$$ =

$${\frac{1}{k}} \left(\vphantom{k_1 \log 2k_1 + k_2 \log 2k_2}\right. \left.\vphantom{k_1 \log 2k_1 + k_2 \log 2k_2}\right)$$ =

$$\geq \begin{array}{l}\mbox{since the minimum value of} \\\mbox{ the...... is attained at }\\\mbox{$k_1 = k_2$\space giving the value $k$ }\end{array}$$

This contradicts the premise that the average depth of T is < log k.

Thus T cannot be of the form of Tree 2.

Thus in any decision tree with n! leaves, the average path length to a leaf is at least 

log(n!) $$\sim$$O(nlog n)