master theorem

A way to find a tight asymptotic bound for a recurrence is via the master theorem, which requires the form of a recurrence $T(n)$ to be the following:

$$\begin{array}{rl}T(n)& =a\cdot T\left(\frac{n}{b}\right)+f(n)\\ f(n)& =d\cdot n^e\cdot {\log }^{k}n\end{array}$$

$f$ represents the work done in a function call, excluding the subproblems.

Master theorem does not work for all recurrences

Master theorem works for divide and conquer recurrences that matches the recurrence form. You may need to find another method (e.g. recurrence tree, substitution) for incompatible recurrences.

Constant	Meaning
$a$	Number of subproblems per problem. This applies recursively to subproblems, so each subproblem will also have $a$ sub-subproblems.
$b$	The reduction factor, e.g. $b=2$ means each subproblem has half the size of the problem, like in merge sort. This also applies recursively.
$d$	Constant factor cost of a function call, i.e. cost of splitting the problem and combining solutions. This won’t matter for asymptotic runtime analysis.
$e$	Exponential cost of a function call, i.e. cost of splitting the problem and combining solutions.
$k\ge 0$	Power on the logarithm.

Once we have $T(n)$ in the above form, we can use the master theorem to find $T(n)=\Theta (g(n))$. Find the case that matches your recurrence from the table below, then prove the corresponding statement in the second column to get the runtime in the third column. You can choose any value of $ϵ>0$ that makes the statement true (by visual inspection), then prove via limit lemma.

If …	then prove that … for some $ϵ>0$	$T(n)=$	Interpretation
${\log }_{b}a>e$	$f(n)=O(n^{{\log }_{b}a-ϵ})$	$\Theta (n^{{\log }_{b}a}$)	Recursion costs asymptotically more than splitting and merging.
${\log }_{b}a=e$	$f(n)=\Theta (n^{{\log }_{b}a}{\log }^{k}n),k\ge 0$	$\Theta (n^e\cdot {\log }^{k+1}n)$	Both costs the same asymptotically. There are $\log n$ levels are each level costs $O(n^e)$.
${\log }_{b}a<e$	$f(n)=\Omega (n^{{\log }_{b}a+ϵ})$	$\Theta (n^e)$	Splitting and merging solutions cost asymptotically more than recursion.

The proof is only for educational purposes

If a case matches, then master theorem already guarantees the tight bound without you having to prove the second column (as long as the recurrence matches the recurrence form exactly).

While proving bounds, also find the $c$ that makes the relationship true.