On the law governing recursive partition
De Lege Partitionis Recursivae
Enuntiatio
Theorema (Lex Partitionis Recursivae). Let a recursive process divide a problem of magnitude n into a subproblems each of magnitude n/b, with a ≥ 1 and b > 1, expending work f(n) = Θ(n^d) upon the division and recombination. Then the total cost obeys the recurrence T(n) = a·T(n/b) + f(n), and its growth is decided by a single contest between the exponent d and the critical exponent c = log_b a.
Three regimes follow, and only three. Case I, when d < c: the multitude of leaves overwhelms the work above them, and T(n) = Θ(n^c). Case II, when d = c: every one of the log_b n levels bears equal cost, and the sum acquires a logarithmic factor, T(n) = Θ(n^c log n). Case III, when d > c: the labor at the root dominates the whole descent, and T(n) = Θ(n^d). The critical exponent c is the pivot upon which the entire law turns.
Expressio
import math
def master_class(a: float, b: float, f_exponent: float) -> str:
"""Return the asymptotic class of T(n) = a*T(n/b) + Theta(n^f_exponent),
by the three cases of the Master Theorem.
Parameters
----------
a : number of subproblems, a >= 1
b : shrink factor per level, b > 1
f_exponent : the exponent d such that the per-call work f(n) = Theta(n^d)
Returns a Theta-class string keyed on c = log_b(a), the critical exponent.
>>> master_class(2, 2, 1) # mergesort: 2T(n/2)+Theta(n)
'Theta(n^1 log n)'
>>> master_class(1, 2, 0) # binary search: T(n/2)+Theta(1)
'Theta(n^0 log n)'
>>> master_class(8, 2, 2) # naive 2x2-block matmul: 8T(n/2)+Theta(n^2)
'Theta(n^3)'
>>> master_class(2, 2, 2) # root-dominated: 2T(n/2)+Theta(n^2)
'Theta(n^2)'
"""
if a < 1:
raise ValueError("a must be >= 1")
if b <= 1:
raise ValueError("b must be > 1")
critical = math.log(a) / math.log(b) # c = log_b(a)
tol = 1e-9 # guard the d == c boundary
if f_exponent < critical - tol:
# Case I: leaves dominate. T(n) = Theta(n^c).
return f"Theta(n^{critical:g})"
elif abs(f_exponent - critical) <= tol:
# Case II: levels balanced. T(n) = Theta(n^c log n).
return f"Theta(n^{critical:g} log n)"
else:
# Case III: root dominates. T(n) = Theta(n^d).
return f"Theta(n^{f_exponent:g})"
# Concrete demonstrations of correctness:
assert master_class(2, 2, 1) == "Theta(n^1 log n)" # mergesort -> n log n
assert master_class(1, 2, 0) == "Theta(n^0 log n)" # binary search -> log n
assert master_class(8, 2, 2) == "Theta(n^3)" # c = log_2 8 = 3, Case I
assert master_class(2, 2, 2) == "Theta(n^2)" # c = 1 < 2, Case III
assert master_class(7, 2, 2) == "Theta(n^2.80735)" # Strassen: c = log_2 7
if __name__ == "__main__":
import doctest
doctest.testmod(verbose=True)Demonstratio
We derive the law by the recursion-tree argument: we account for the total work by summing the cost of every node in the tree of recursive calls, level by level.
1. The shape of the tree. The root holds the problem of size n and expends f(n) at that node alone. It spawns a children, each of size n/b; each child spawns a of its own, of size n/b²; and so on. At level i (the root being level 0) there are a^i nodes, each of size n/b^i. The recursion halts when the size reaches 1, i.e. when n/b^i = 1, hence at level i = log_b n. The tree therefore has exactly log_b n + 1 levels.
2. The work at one level. Each node at level i has size n/b^i and so expends f(n/b^i) = Θ((n/b^i)^d) work upon its own division. Multiplying by the a^i nodes present, the work summed across level i is
W_i = a^i · Θ((n/b^i)^d) = Θ(n^d) · (a / b^d)^i.
The level-work is thus a geometric progression in i with common ratio r = a / b^d. Note that r compares a against b^d: taking logarithms base b, r ⪋ 1 exactly as d ⪋ log_b a = c. The single contest d versus c governs everything.
3. The leaf count. At the bottom level i = log_b n there are a^(log_b n) nodes. By the identity a^(log_b n) = n^(log_b a) = n^c, the tree has Θ(n^c) leaves, each contributing Θ(1). The leaves alone therefore cost Θ(n^c). This quantity is the lower bound below which T(n) can never fall.
4. Summing the three regimes. The total is T(n) = Σ_{i=0}^{log_b n} Wi = Θ(n^d) · Σ{i=0}^{log_b n} r^i, plus the Θ(n^c) leaf term. We evaluate the geometric sum by the value of r.
Case I — d < c, so r > 1. The series is dominated by its last term: a geometric sum with ratio r > 1 over k terms is Θ(r^k). Here k = log_b n, so Θ(n^d) · r^(log_b n) = Θ(n^d) · (a/b^d)^(log_b n) = Θ(n^d) · n^(log_b a) / n^d = Θ(n^c). The work piles up toward the leaves; the leaf term Θ(n^c) prevails. Hence T(n) = Θ(n^c).
Case II — d = c, so r = 1. Every level costs the same Θ(n^d), and there are log_b n + 1 of them. The sum is Θ(n^d) · (log_b n + 1) = Θ(n^c log n), the logarithmic factor arising directly from the count of equal-cost levels. Hence T(n) = Θ(n^c log n).
Case III — d > c, so r < 1. The series is dominated by its first term: a decreasing geometric series with ratio r < 1 converges, Σ_{i≥0} r^i = 1/(1−r) = Θ(1). Thus the sum is Θ(n^d) · Θ(1) = Θ(n^d), which already absorbs the smaller leaf term Θ(n^c) since d > c. The root’s labor dominates the descent. Hence T(n) = Θ(n^d).
5. Closure. The three cases exhaust the trichotomy d < c, d = c, d > c, and the value of each is read off the geometric ratio r = a/b^d. The pivot is c = log_b a in every instance. This is a derivation by the recursion-tree heuristic: it presumes f(n) = Θ(n^d) of exact polynomial order and treats n as an exact power of b, leaving aside the regularity conditions and floor/ceiling adjustments a fully rigorous proof would discharge.
Q.E.I.