Recursion Trees
-
Since the substitution method involves having to guess the solution, it might often be difficult to effectively use it. We can use recursion trees to devise a good guess. In a recursion tree, each node represents the cost of a single subproblem somewhere in the set of recursive function invocations. We sub the costs within each level of the tree to obtain a set of per-level costs, and then we sum all the per-level costs to determine the total cost of all levels of recursion.
-
So let’s use an example to show the recursion tree method! Suppose we wanted to solve .
-
Guessing a correct solution might be difficult and expanding the recurrence might be difficult, so let’s draw a recursion tree.
The recursion tree will represent the sum of the number of steps the recurrence has to do on each level. From the original recurrence equation, , so we’ll use the notation in the above to represent this sum.
Now let’s expand and . We know hat and that . So we can just substitute those relations in the recurrence tree.
We can keep expanding the tree, and eventually we’ll reach a base case. (We’ll assume .)
Now let’s count the cost on each level. We’ll just sum the number of nodes.
The total cost will be . We’ll assume that the pattern continues and that the total sum is . If we rearrange the equation, we’ll get . It turns out that is a constant less than two (since ). So the total cost is . (You could indeed see that from the fact that was the value at the root of the tree.)
-
Since the recursion tree method has some ambiguities (such as the … in the diagram), it is a very good tool to come up with a “guess” to later verify using the substitution method.