# Recursion tree study problems

### Problem 1

Let's define a function T as follows (powers of 3 only)

- T(9) = 7
- T(n) = 4 T(n/3) + n

Answer the following questions about the recursion tree
for this function:

- How many nodes are in the fifth level of the tree?
(Assuming that n is large enough that the tree has a fifth level.)
- What is the sum of the values of all nodes in the fifth level?
- What is the height of the tree?
- How many leaves does the tree have?

solution

### Problem 2

Let's define a function T as follows:

- T(1) = c
- T(n) = nT(n-1) + 1

Answer the following questions about the recursion tree
for this function:

- How many nodes are in the third level of the tree?
- What is the height of the tree?
- What is the sum of the values in the leaf nodes of the tree?
- Is the closed form for this function \(O(2^n)\)?

solution