2. Iteration Methods
It means to expand the recurrence and express it as a summation of terms of n and initial condition.
Example1: Consider the Recurrence
3.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 T (n) = 2T  + n2We have to obtain the asymptotic bound using recursion tree method. Solution: The Recursion tree for the above recurrence is  |
0 Comments