Master Theorem

The Master Theorem applies to recurrences of the following form:

$T(n)=aT(\frac{n}{b})+f(n)$

where $a1$ and $b>1$ are constants and $f(n)$ is an asymptotically positive function.

There are $3$ cases:

If $f(n)=O(n^{lo{g}_{b}a-lon})$ for some constant $lon>0,$ then $T(n)=(n^{lo{g}_{b}a}).$

If $f(n)=(n^{lo{g}_{b}a}lo{g}^{k}n)$ with ${?}^{1}k0,$ then $T(n)=(n^{lo{g}_{b}a}lo{g}^{k+1}n).$

If $f(n)=(n^{lo{g}_{b}a+lon})$ with $lon>0,$ and $f(n)$ satisfies the regularity condition, then $T(n)=(f(n)).$ Regularity condition: $af(\frac{n}{b})cf(n)$ for some constant $c<mn\; id="EditorElement\_157948">1</mn>$ and all sufficiently large $n$ :

Practice Problems

For each of the following recurrences, give an expression for the runtime $T(n)$ if the recurrence can be solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply.

$T(n)=3T(\frac{n}{2})+n^2$

$T(n)=4T(\frac{n}{2})+n^2$

$T(n)=T(\frac{n}{2})+2^n$

$T(n)=2^{n}T(\frac{n}{2})+n^n$

$T(n)=16T(\frac{n}{4})+n$

$T(n)=2T(\frac{n}{2})+nlogn$

${?}^1$ most of the time, $k=0$