# 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}\)