the Akra-Bazzi method
/ AH-krah BAH-zee /
The Master Theorem is wonderfully tidy but rigid: it insists all subproblems have the same size n/b. Real algorithms sometimes split unevenly — one piece of size n/3 and another of size 2n/3, say — and then the Master Theorem simply does not apply. The Akra-Bazzi method is the more powerful tool that handles these messy, uneven recurrences.
It solves recurrences of the form T(n) = sum over i of a_i T(n / b_i) + f(n), where the subproblems can have different shrink factors b_i and different multiplicities a_i. The recipe: first find the single number p that solves the equation sum over i of a_i / (b_i)^p = 1. This p generalises the critical exponent log_b a (in the equal-split case it gives exactly that). Then T(n) = Theta( n^p * (1 + integral from 1 to n of f(u) / u^(p+1) du) ). In words: n^p is the leaf benchmark, and the integral measures how much the combine work f contributes relative to that benchmark across all scales. If f is small the n^p term wins; if f is large the integral wins; the formula blends them automatically.
Akra-Bazzi is the right tool whenever splits are unequal, whenever you add small lower-order shifts like T(floor(n/2)) + T(ceil(n/2)), or whenever you want to confirm a Master-Theorem result holds despite rounding. The honest trade-off: the integral can be fiddly, and the method (in its standard form) still wants the subproblem sizes to be n/b_i up to small perturbations and f to be reasonably well-behaved (polynomial-growth, satisfying a mild smoothness condition). For the common cases, though, it cleanly recovers every Master-Theorem answer and many it cannot reach.
Median-of-medians selection: T(n) = T(n/5) + T(7n/10) + Theta(n). Solve (1/5)^p + (7/10)^p = 1; the solution is p < 1, and since f(n) = n grows faster than n^p the integral dominates, giving T(n) = Theta(n) — linear-time selection, which the Master Theorem cannot show because the split is uneven.
Solve sum a_i / b_i^p = 1 for p, then evaluate the integral to blend leaf work with combine work.
Akra-Bazzi generalizes the Master Theorem but is not unlimited: f still needs a mild smoothness (polynomial-type growth) condition, and the sizes must be n/b_i up to small perturbations. It does not magically solve recurrences like T(n) = T(n-1) + 1 that are not divide-and-conquer in shape.