wild-inter.net Divide & conquer recurrences

The Master Theorem

\(\ca{a}\) \(\cb{b}\) \(\cd{d}\)
\(\cf{f}(n) \rel=\) \(n\) \(\cdot\,\lg\)\(n\)
Recursion tree
The balance
Side conditions  ·  regularity, rounding, and when you may skip both

The regularity condition

Case (c) needs it, and it is the only genuinely technical part of the theorem:

\(\exists n_1, \rho \lt 1\ \ \forall n \ge n_1 : \ \ \ca{a}\cdot\cf{f}(n/\cb{b}) \rel\le \rho\,\cf{f}(n)\)

It says the children’s conquer work is a constant factor smaller than the parent’s — so the sum over the levels is a decaying geometric series and the root really does pay for everything.

Lemma (regularity condition). If \(\cf{f}(n) \sim B\,n^{\alpha}\log^{\gamma}(n)\) for constants \(B > 0\), \(\gamma\) and \(\alpha > \cc{c} = \log_{\cb{b}}(\ca{a})\), the regularity condition holds. (Asymptotic equivalence \(\sim\), not just \(\Theta\): a \(\Theta\) allows \(\cf{f}\) to oscillate, and that can break it.)

What about rounding?

For general \(n\) the subproblems are \(\lfloor n/\cb{b}\rfloor\) and \(\lceil n/\cb{b}\rceil\). In general that matters — but:

Lemma (polynomial-growth master method). If \(\cf{f}\) satisfies the polynomial-growth condition, the \(\Theta\)-class of the solution is the same with or without floors and ceilings.

\(\exists n_0\ \forall C \ge 1\ \exists D > 1\ \ \forall n \ge n_0\ \forall t \in [1, C] : \ \ \tfrac1D\,\cf{f}(n) \rel\le \cf{f}(tn) \rel\le D\,\cf{f}(n)\)

Growing \(n\) by up to a constant factor \(C\) changes the function value by at most a constant factor \(D = D(C)\), for large enough \(n\). In particular every \(\cf{f}(n) = \Theta\bigl(n^{\alpha}\log^{\gamma}(n)\log\log^{\delta}(n)\bigr)\) qualifies — zero exponents allowed.

Where the master theorem says nothing

Load an example  ·  plain-text recurrence format
One key value per line. Everything is optional; omitted keys keep their current value.
name label shown in the dropdown
a number of subproblems
b shrink factor (fractions ok: 10/7)
d base-case cost (≥ 0)
f B alpha gamma for \(B\,n^{\alpha}\lg^{\gamma} n\),
   e.g. f 1 1 1 is \(n\lg n\)
terms Roura mode: a b, a b, …
k number of growth steps before the long run
note a line of commentary (TeX in \(…\))