# 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

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

### Problem 2

Let's define a function T as follows:

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

4. Is the closed form for this function $$O(2^n)$$?