The Akra–Bazzi Method

The master theorem is a beautiful tool with one rigid demand: all subproblems must be the same size, n/b. Real algorithms often break that rule. The linear-time median-of-medians selection recurses on a fifth of the data and on seven-tenths of it — T(n) = T(n/5) + T(7n/10) + n — two different shrink factors in one line. The master theorem simply cannot read this recurrence; it has no single b to offer.

The Akra–Bazzi method (Mohamad Akra and Louay Bazzi, 1998) is the master theorem's grown-up successor. It handles any number of subproblems, each with its own size fraction, even with small perturbations to those sizes — and it recovers the master theorem exactly as a special case. Where the master theorem gives a lookup table, Akra–Bazzi gives a formula: solve one equation for an exponent, then evaluate one integral.

Why uneven splits break the master theorem

Look again at what the master theorem needs: a recurrence T(n) = a\,T(n/b) + f(n) with a single count a and a single ratio b. Its whole engine — the watershed n^{\log_b a}, the three cases — is built from that one b. Now consider these, all common in practice:

Two unequal splits. T(n) = T(n/3) + T(2n/3) + n — the cost of a run of certain balanced-tree and interval algorithms. Fractions 1/3 and 2/3 differ, so there is no single b.
Median-of-medians selection. T(n) = T(n/5) + T(7n/10) + n — the recurrence behind worst-case linear selection. Again two different fractions.
The log-factor blind spot. T(n) = 2\,T(n/2) + n/\log n — even split, but f sits only a \log away from the watershed, in the master theorem's gap. Akra–Bazzi's integral handles it head-on.

The method in two steps

Write the recurrence in the general Akra–Bazzi form — a sum of terms, each with its own multiplicity a_i > 0 and shrink fraction 0 < b_i < 1, plus a driving function g(n):

T(n) = \sum_{i=1}^{k} a_i\, T(b_i\, n) + g(n).

Step 1 — find the exponent p. Solve the single equation \sum_{i=1}^{k} a_i\, b_i^{\,p} = 1. The left side decreases from \sum a_i (at p = 0) toward 0, so there is exactly one real root p. This p plays the role of the master theorem's \log_b a.
Step 2 — evaluate the integral. Then T(n) = \Theta\!\left(n^{p}\left(1 + \int_{1}^{n} \frac{g(u)}{u^{\,p+1}}\, du\right)\right). The n^p is the leaf cost; the integral measures how much the driving work g adds on top.

That is the entire method. Everything else is arithmetic: solve for p, plug in g, integrate. The chart shows step 1 for the T(n/3) + T(2n/3) + n recurrence: the curve (1/3)^p + (2/3)^p falls through the line = 1 exactly at p = 1.

Worked example: T(n) = T(n/3) + T(2n/3) + n

Here a_1 = a_2 = 1, b_1 = 1/3, b_2 = 2/3, and g(n) = n.

Step 1. Solve (1/3)^p + (2/3)^p = 1. Try p = 1: 1/3 + 2/3 = 1. It fits exactly, so p = 1. (This is no accident — whenever the fractions b_i sum to 1 and each a_i = 1, i.e. you partition the input and recurse on every piece once, p = 1.)

Step 2. With p = 1 and g(u) = u:

\int_{1}^{n} \frac{u}{u^{\,2}}\,du = \int_{1}^{n} \frac{1}{u}\,du = \ln n, \qquad T(n) = \Theta\!\big(n^{1}(1 + \ln n)\big) = \Theta(n\log n).

So this uneven 1/3–2/3 split sorts out to the same \Theta(n\log n) as a clean merge sort — the imbalance costs nothing asymptotically. Now rerun the recipe on median-of-medians, T(n) = T(n/5) + T(7n/10) + n: at p = 1 the sum is 1/5 + 7/10 = 9/10 < 1, so the true root has p < 1. Because g(n) = n grows faster than n^p, the integral \int_1^n u^{-p}\,du = \Theta(n^{1-p}) dominates, and n^p \cdot n^{1-p} = n gives T(n) = \Theta(n) — the celebrated worst-case linear-time selection.

Recurrence	Step 1: \sum a_i b_i^p = 1	p	Result
T(n/3)+T(2n/3)+n	(\tfrac13)^p+(\tfrac23)^p=1	1	\Theta(n\log n)
T(n/5)+T(7n/10)+n	(\tfrac15)^p+(\tfrac{7}{10})^p=1	\approx 0.84	\Theta(n)
2\,T(n/2)+n (merge sort)	2\,(\tfrac12)^p=1	1	\Theta(n\log n)

Take a single-term recurrence T(n) = a\,T(n/b) + f(n) — the master theorem's home turf. In Akra–Bazzi form there is one term with a_1 = a and b_1 = 1/b, so step 1 reads a\,(1/b)^p = 1, i.e. b^p = a, i.e. p = \log_b a — exactly the master theorem's watershed exponent. Then the integral \int_1^n f(u)/u^{p+1}\,du reproduces all three cases: it converges (root wins → case 1's leaf term n^p), grows like a log (the tie → case 2's extra \log n), or grows like f itself (case 3). One formula, and the whole three-case table falls out. Akra–Bazzi doesn't replace the master theorem so much as explain it.

The commonest slip is to grab a familiar exponent instead of actually solving \sum a_i b_i^p = 1. For T(n) = T(n/3) + T(2n/3) + n there is no single b, so "\log_b a" is meaningless — you must solve (1/3)^p + (2/3)^p = 1, which happens to give p = 1. Equally, don't assume more subproblems always means a bigger p: for median-of-medians the fractions sum to less than 1, pulling p below 1 to about 0.84, and the driving term g(n) = n then dominates the whole answer. Always run step 1 honestly — the exponent p is defined by the equation, never guessed from the shape.