From recurrence tree analysis we know that the total work is given by:

$$ T(n) = \sum^{\log_cn}_{i = 0}r^i\cdot f\left(\frac{n}{c^i}\right) $$

Source: P.50 Erickson Text

Where:

• $c$ is the how much we reduce the problem
• $r$ is the number of recursive calls
• $\log_c n$ is the depth of the tree

@Hint I know there are conflicting variable names but I really wanted to reference this graph :(

Thm. Masters Theorem

For a runtime function $T(n)$ given by:

$$ T(n)=a\cdot T\left(\frac nb\right) + f(n) $$

where $a, b, n\in \Bbb N$ and they represent:

• $a$: number of recursive calls
• $b$: how much we reduce the problem
• $f(n)$ : work at each level.

@EX

$$ T(n)=3T\left(\dfrac n4\right) + n^2 $$

In this case $a = 3, b=4, f(n)=n^2$.

It means the main routine does 3 recursive calls, each with a problem size $\frac n4$, and the work at each level is $n^2$

We have 3 cases depending on $n^{\log_ba}$ vs. $f(n)$