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(n4)+T(n2)+n2T(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.

    tree 3.svg

    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(n4)+T(n2)+n2T(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(n4)T\left( \frac{n}{4} \right) and T(n2)T\left( \frac{n}{2} \right). We know hat T(n4)=T(n16)+T(n8)+(n4)2T\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(n2)=T(n8)+T(n4)+(n2)2T\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.

    tree 4.svg

    We can keep expanding the tree, and eventually we’ll reach a base case. (We’ll assume T(1)=Θ(1)T(1) = \Theta(1).)

    tree 5.svg

    Now let’s count the cost on each level. We’ll just sum the number of nodes.

    tree 6.svg

    The total cost will be n2+516n2+25256n2+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 i=0(516)in2\sum\limits ^{\infty }_{i = 0} \left( \dfrac {5}{16} \right)^i n^2. If we rearrange the equation, we’ll get (1+516+25256+)n2\left( 1 + \dfrac{5}{16} + \dfrac{25}{256} + \cdots \right) n^2. It turns out that (1+516+25256+)\left( 1 + \dfrac{5}{16} + \dfrac{25}{256} + \cdots \right) is a constant less than two (since 1+12+14+=21 + \dfrac{1}{2} + \dfrac{1}{4} + \cdots = 2). So the total cost is i=0(516)in2<2n2Θ(n2)\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 n2n^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.

results matching ""

    No results matching ""