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 perlevel costs, and then we sum all the perlevel 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 $T(n) = T\left( \frac{n}{4} \right) + T \left( \frac {n}{2} \right) + n^2$.

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, $T(n) = T\left( \frac{n}{4} \right) + T \left( \frac {n}{2} \right) + n^2$, so we’ll use the notation in the above to represent this sum.
Now let’s expand $T\left( \frac{n}{4} \right)$ and $T\left( \frac{n}{2} \right)$. We know hat $T\left( \frac{n}{4} \right) = T\left( \frac{n}{16} \right) + T \left( \frac {n}{8} \right) + \left( \frac{n}{4} \right)^2$ and that $T\left( \frac{n}{2} \right) = T\left( \frac{n}{8} \right) + T \left( \frac {n}{4} \right) + \left( \frac{n}{2} \right)^2$. 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 $T(1) = \Theta(1)$.)
Now let’s count the cost on each level. We’ll just sum the number of nodes.
The total cost will be $n^2 + \frac{5}{16} n^2 + \frac{25}{256} n^2 + \cdots$. We’ll assume that the pattern continues and that the total sum is $\sum\limits ^{\infty }_{i = 0} \left( \dfrac {5}{16} \right)^i n^2$. If we rearrange the equation, we’ll get $\left( 1 + \dfrac{5}{16} + \dfrac{25}{256} + \cdots \right) n^2$. It turns out that $\left( 1 + \dfrac{5}{16} + \dfrac{25}{256} + \cdots \right)$ is a constant less than two (since $1 + \dfrac{1}{2} + \dfrac{1}{4} + \cdots = 2$). So the total cost is $\sum\limits ^{\infty }_{i = 0} \left( \dfrac {5}{16} \right)^i n^2 < 2n^2 \in \Theta \left( n^2 \right)$. (You could indeed see that from the fact that $n^2$ 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.