Solving Recurrences & the Master Theorem

A recurrence expresses an algorithm's cost $T(n)$ in terms of its cost on smaller inputs. Every divide-and-conquer algorithm that breaks a size-$n$ problem into $a$ subproblems of size $n/b$ and spends $f(n)$ extra work to split and combine obeys

$T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n),\qquad a\ge 1,\; b>1.$

Solving it means finding the asymptotic order of $T(n)$.

The Master Theorem

Compare $f(n)$ against the watershed function $n^{\log_b a}$ (the number of leaves in the recursion tree). Let $c^{*}=\log_b a$.

Case 3 additionally needs the regularity condition $a\,f(n/b)\le c\,f(n)$ for some constant $c<1$. The workhorse is Case 2 with $k=0$: $a\,T(n/b)+\Theta\!\left(n^{c^{*}}\right)=\Theta\!\left(n^{c^{*}}\log n\right)$ — exactly merge sort, $2T(n/2)+n=\Theta(n\log n)$.

Recipe

1. Read off $a$, $b$, and $f(n)$.
2. Compute $c^{*}=\log_b a$ and the watershed $n^{c^{*}}$.
3. Decide whether $f$ is polynomially smaller (Case 1), the same order up to logs (Case 2), or polynomially larger (Case 3).

Mini-example. $T(n)=3T(n/2)+n$: here $c^{*}=\log_2 3\approx 1.58$ and $f(n)=n=O\!\left(n^{\,1.58-\epsilon}\right)$, so Case 1 gives $T(n)=\Theta\!\left(n^{\log_2 3}\right)$.

When the Master Theorem doesn't apply

Square-root recurrences. For $T(n)=a\,T(\sqrt{n})+f(n)$, substitute $n=2^{m}$ (so $m=\log n$) and set $S(m)=T(2^{m})$; then $\sqrt{n}=2^{m/2}$ turns the square root into a halving:

$T(n)=2T(\sqrt{n})+\log n \;\Longrightarrow\; S(m)=2S\!\left(\tfrac{m}{2}\right)+m=\Theta(m\log m),$

and back-substituting $m=\log n$ gives $T(n)=\Theta(\log n\,\log\log n)$. A floor such as $\lfloor\sqrt{n}\rfloor$ never changes the asymptotics.

Subtract-and-conquer & halving. $T(n)=T(n-1)+\Theta(n)=\Theta(n^{2})$ (insertion/selection-sort worst case); $T(n)=2T(n-1)+\Theta(1)=\Theta(2^{n})$; and the pure halving search $T(n)=T(n/2)+\Theta(1)=\Theta(\log n)$ — e.g. shrinking a region of $16$ down to $1$ by comparing halves takes $\log_2 16=4$ steps.

Setting up the recurrence is half the battle. Naming the true subproblem sizes matters more than the algebra: a quicksort whose pivot is the median of a $\Theta(\sqrt{n})$ sample guarantees at least $\sqrt{n}$ elements on each side, so its worst-case split is the lopsided $T(\sqrt{n})+T(n-\sqrt{n})+\Theta(n)$ — not the balanced $2T(n/2)$ that the word "median" might suggest.

Exam trick: Reach for the Master Theorem only once the recurrence already has the exact shape $a\,T(n/b)+f(n)$. A $\sqrt{n}$ argument means substitute $n=2^{m}$; two different subproblem sizes mean Akra–Bazzi or a recursion tree; an $n-b$ argument (not $n/b$) means subtract-and-conquer, so unroll the sum instead.