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 $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.