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:

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?

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:

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

solution