Recursion Tree Method
1. Recursion Tree Method is a pictorial representation of an iteration method which is in the form of a tree where at each level nodes are expanded.
2. In general, we consider the second term in recurrence as root.
3. It is useful when the divide & Conquer algorithm is used.
4. It is sometimes difficult to come up with a good guess. In Recursion tree, each root and child represents the cost of a single subproblem.
5. We sum the costs within each of the levels of the tree to obtain a set of pre-level costs and then sum all pre-level costs to determine the total cost of all levels of the recursion.
6. A Recursion Tree is best used to generate a good guess, which can be verified by the Substitution Method.
Example 1
Consider T (n) = 2T+ n2
+ n2 We have to obtain the asymptotic bound using recursion tree method.
Solution: The Recursion tree for the above recurrence is
Example 2: Consider the following recurrence
T (n) = 4T
Obtain the asymptotic bound using recursion tree method.
Solution: The recursion trees for the above recurrence
Example 3: Consider the following recurrence
Obtain the asymptotic bound using recursion tree method.
Solution: The given Recurrence has the following recursion tree
When we add the values across the levels of the recursion trees, we get a value of n for every level. The longest path from the root to leaf is
