Where the master theorem runs out of road
The previous guide gave you the master theorem, a fast lookup for the single shape T(n) = a T(n/b) + f(n). Its quiet assumption is uniformity: there are exactly a subproblems and every one of them shrinks by the very same factor b. That covers a huge slice of divide-and-conquer recurrences — but real algorithms keep stepping outside the lines. The moment your subproblems are different sizes, the master theorem has nothing to say, and you are stuck reaching for a recursion tree by hand.
The canonical troublemaker is median-of-medians selection, the algorithm that finds the k-th smallest element in guaranteed linear time. It recurses on two pieces of different sizes: a call on about n/5 elements to find a pivot, then a call on at most about 7n/10 elements after partitioning, plus linear work. That gives T(n) = T(n/5) + T(7n/10) + Theta(n) — an honest uneven-split recurrence. There is no single b here: one piece shrinks by 5, the other by 10/7. The master theorem cannot even be stated for this, yet the algorithm is famous precisely because its answer comes out Theta(n).
The Akra-Bazzi shape
Akra-Bazzi solves a much roomier family. Instead of one term a T(n/b), it allows a sum of terms, each with its own multiplicity and its own shrink factor: T(n) = sum from i=1 to k of a_i T(n/b_i) + f(n). Here you may have k different subproblem groups; group i appears a_i times and each of its pieces has size n/b_i, where the a_i are positive and each b_i is strictly greater than 1. The driving work f(n) is allowed to be any reasonably well-behaved function — and crucially, the method does not blink at the small distortions real code produces, like recursing on floor(n/2) instead of exactly n/2, or on n/5 + 3.
master theorem : T(n) = a*T(n/b) + f(n) (one b, every piece same size)
Akra-Bazzi : T(n) = SUM_i a_i*T(n/b_i) + f(n) (many b_i, pieces differ)
example (median-of-medians):
T(n) = 1*T(n/5) + 1*T(7n/10) + Theta(n)
a_1=1,b_1=5 a_2=1,b_2=10/7 f(n)=nNotice that the master theorem is simply the case k=1: one group, a_1 = a, b_1 = b. So Akra-Bazzi is not a different idea bolted on — it is the same idea with the dial turned all the way up. Everything you learned about reading a and b off the code still applies; you just read off a whole list of (a_i, b_i) pairs instead of one pair, exactly the way you already learned to write the recurrence straight from the recursive calls.
The magic exponent p
The whole method turns on one number, written p, that plays the exact role the critical exponent log base b of a played in the master theorem. You find p by solving the equation sum from i=1 to k of (a_i / b_i^p) = 1. In words: choose the power p that makes the subproblem sizes, raised to that power and added up, balance out to exactly 1. There is always exactly one such p (the left side smoothly decreases as p grows), and for the single-term master case this equation reads a / b^p = 1, which is just a = b^p — the familiar p = log base b of a in disguise.
Once you have p, Akra-Bazzi hands you the answer through an integral that compares the driving work f(n) against the threshold growth n^p, summed over all scales: T(n) = Theta( n^p * (1 + integral from 1 to n of f(u)/u^(p+1) du) ). That integral looks intimidating, but it is doing the same bookkeeping as a recursion tree — adding up f's contribution across every level, weighted by how the subproblems multiply — only in closed form. The n^p out front is the cost the leaves contribute; the integral is the cost the internal levels contribute.
- Write the recurrence as a sum: read off each group's multiplicity a_i and shrink factor b_i, plus the driving work f(n).
- Solve sum of a_i / b_i^p = 1 for the unique exponent p (for one term this is just p = log base b of a).
- Evaluate the integral of f(u)/u^(p+1) from 1 to n — it tells you whether the leaves or the top levels dominate.
- Read T(n) = Theta( n^p * (1 + that integral) ); if the integral converges you get Theta(n^p), if it grows you get f's contribution back.
Working it on median-of-medians
Take T(n) = T(n/5) + T(7n/10) + Theta(n). Here both groups have multiplicity 1, with b_1 = 5 and b_2 = 10/7, and f(n) = n. First find p from (1/5^p) + (7/10)^p = 1. Try p = 1: that is 1/5 + 7/10 = 0.2 + 0.7 = 0.9, which is less than 1. Since the left side decreases as p grows, and at p = 1 it is already below 1, the true p must be less than 1. So n^p grows slower than n, meaning the linear driving work f(n) = n outweighs the leaf term.
Now the integral of u / u^(p+1) = u^(-p) from 1 to n. Since p < 1, the exponent 1 - p is positive, so this integral grows like n^(1-p). Multiply by the n^p out front and the powers of n cancel beautifully: n^p * n^(1-p) = n^1. The answer is T(n) = Theta(n) — the median-of-medians runs in linear time, derived in three honest lines instead of a delicate tree argument. That cancellation, where f(n) is the heavyweight and you simply get Theta(f(n)), is Akra-Bazzi's version of the master theorem's third case.
Honest limits and when not to reach for it
Akra-Bazzi is general but not universal, and the boundaries are worth knowing. It still needs every b_i strictly greater than 1 — each subproblem must genuinely shrink by a constant factor. So it does not solve decrease-by-one recurrences like quicksort's worst case T(n) = T(n-1) + Theta(n); that is a shrink-by-subtraction recurrence, not shrink-by-division, and you unroll it directly to O(n^2). The driving f(n) must also satisfy a mild smoothness condition (a bound on how fast it can change), which every polynomial, logarithm, and their products easily meet, but pathological oscillating functions do not.
There is also a practical caution: a slicker theorem does not change what the answer means. The Theta you compute is still pure asymptotics, so the usual disclaimers stand. Big-O hides constants and low-order terms, so this describes how the time scales for large n, not a verdict at small sizes; and the recurrence you fed in is tied to one case — median-of-medians earns its Theta(n) in the worst case, but a different selection method might be asked about on average instead. Always know which case your f(n) and split sizes describe before you trust the integral's verdict.
So keep both tools on your belt. Reach for the master theorem first when the recurrence is the clean a T(n/b) + f(n) shape — it is faster and its three cases are easy to remember. Reach for Akra-Bazzi when the pieces are different sizes, when there are several of them, or when the +c and floor/ceiling clutter would make you nervous about the master theorem's fine print. Between the recursion tree for intuition, substitution for proof, the master theorem for speed, and Akra-Bazzi for generality, you can now solve essentially every recurrence a divide-and-conquer algorithm will throw at you.