Recursion Tree

Starting to get closer to an ``automated'' approach.

Take T(n) = 2 T(n/2) + n².

Imagine recursion unfolding as a tree . $\epsfig {file=figs04/clr4.1.ps,width=4.5in}$

A harder version: T(n) = T(n/3)+T(2n/3)+n.

$\epsfig {file=figs04/clr4.2.ps,width=4.5in}$

Next: Summary Up: SOLVING RECURRENCES Previous: The Table Method