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

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 +n 

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