Recursion trees Problem 1

Here is the definition of T for reference:
• T(9) = 7
• T(n) = 4 T(n/3) + n

Solution

Notice that the tree has 4-way branching and the problem size decreases by a factor of 3 at each level.

(a) There are $$4^5$$ nodes in the fifth level of the tree.

(b) Each node in the fifth level contains the value $$n/3^5$$. So the sum of all the nodes in the fifth level is $$4^5 \cdot n /3^5 = n(4/3)^5$$ .

(c) The height of the tree is the level of the leaves. We reach the leaf level when $$n/3^k$$ equals the input for the base case, which is 9. So we need to solve $$n/3^k = 9$$ for k.

$$n/3^k = 9$$ is equivalent to $$n = 3^{k+2}$$. That is $$\log_3 n = k+2$$. So $$k = \log_3 n-2$$.

So the height of the tree is $$h = \log_3 n-2$$.

(d) Since the branching factor is 4, there are $$4^h$$ leaves. That is, $$4^{\log_3 n-2}$$ leaves

Simplifying this, we have $$4^{\log_3 n-2} = \frac{1}{16}4^{\log_3 n}$$. But $$4^{\log_3 n} = 4^{\log_4 n \log_3 4} = (4^{\log_4 n})^{\log_3 4} = n^{\log_3 4}$$ So the number of leaves is $$\frac{1}{16}n^{\log_3 4}$$