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.)
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.
Let \(T(n)\) be recursively defined as
where \(D \in \mathbb N\), \(\ca{a_d} > 0\), \(\cb{b_d} > 1\), for \(d = 1, \ldots, D\) are constants, functions \(r_{n,d}\) satisfy \(|r_{n,d}| = O(1)\) as \(n \to \infty\), and function \(\cf{f}(n)\) satisfies \(\cf{f}(n) \sim B\cdot n^{\alpha}(\ln n)^{\gamma}\) for constants \(B > 0\), \(\alpha\), \(\gamma\).
Set \(H = 1 - \sum_{d=1}^{D} \ca{a_d}\,(1/\cb{b_d})^{\alpha}\); then we have:
Two things the master theorem cannot do are built in here: the subproblem sizes \(\cb{b_d}\) may differ from each other, and the shift \(r_{n,d}\) absorbs floors and ceilings, so no separate rounding lemma is needed. The base-case values \(c_n\) are arbitrary; they do not affect the \(\Theta\)-class, though they do affect constants below the leading term.
The Terms box holds one a b pair per subproblem size, separated by commas — the
\(\ca{a_d}\) and \(\cb{b_d}\) above. Fractions are allowed. So 2 2 means \(2\,T(n/2)\),
and 1 5, 1 10/7 means \(T(n/5) + T(7n/10)\) — the median-of-medians recurrence. The
\(\cf{f}(n)\) boxes then give \(\alpha\) and \(\gamma\); they are written in \(\lg\) here and
converted to \(\ln\) internally, which only changes the constant \(B\).
key value per line. Everything is optional;
omitted keys keep their current value.name label shown in the dropdowna number of subproblemsb shrink factor (fractions ok: 10/7)d base-case cost (≥ 0)f B alpha gamma for \(B\,n^{\alpha}\lg^{\gamma} n\),f 1 1 1 is \(n\lg n\)terms Roura mode: a b, a b, …k number of growth steps before the long runnote a line of commentary (TeX in \(…\))