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