Recursion Trees

Internal

• Recursive Algorithms Complexity
• Merge Sort

Overview

The idea behind the recursion tree method is to write out the work done by the recursive algorithm in a tree structure, where the children of a given node represent the recursive calls made by that node. The tree will facilitate counting the overall work done by the algorithm and facilitate the analysis.

The bottom-most level is log₂n because the problem size is decreased by a factor of 2 at each level of recursion, and the bottom-most level problem size is 1, so:

1 = n/2m → n = 2m → m = log2n

The analysis reveals that at the level j of the recursion there are 2^j subproblems and each subproblem has a size of n/2^j.

TODO

Redo after class.

The method consists in converting the recurrence into graphical tree representation whose nodes represent costs incurred at various level of the recursion. After we lay out the tree, we sum the costs within each level of the tree to obtain a set of per-level costs, then we sum all the per-level costs to determine the total cost of the recursion. The bound such guessed can be proven with the substitution method. Examples on how to build recursion trees are available in CLRS page 37 and page 88.

[Next]