Recursion tree
= Recursion tree
A <recursion tree> records recursive calls as nodes and their direct recursive subcalls as children. Its node labels can record the work done outside those subcalls. Summing the work over levels or charging it to nodes proves a total <running time> bound. For $T(n)=aT(n/b)+f(n)$, level $j$ has approximately $a^j$ instances of size $n/b^j$, so its nonrecursive work is $a^jf(n/b^j)$. Summing those quantities explains the cases of the <master theorem>.