Akra–Bazzi theorem

Builds on Big O notation Recurrence relation

Statement

Let $k \ge 1$ , and let $a_1, \dots, a_k > 0$ and $0 < b_1, \dots, b_k < 1$ be real constants. Let $g \colon [1, \infty) \to [0, \infty)$ satisfy the polynomial growth condition: there are constants $c_1, c_2 > 0$ such that $c_1 g(x) \le g(u) \le c_2 g(x)$ for all $x \ge 1$ , all $i$ and all $u \in [b_i x, x]$ . Let $h_1, \dots, h_k$ be real functions with $\abs{h_i(x)} = O(x / (\log x)^2)$ , in big O notation. Let $x_0$ be large enough, and let $T \colon [1, \infty) \to \R$ be positive and bounded above and below by positive constants on $[1, x_0]$ , and satisfy the recurrence $T(x) = g(x) + \sum_{i=1}^{k} a_i\, T\big(b_i x + h_i(x)\big) \qquad (x > x_0).$ Let $p$ be the unique real number with $\sum_{i=1}^{k} a_i b_i^p = 1$ . Then $T(x) = \Theta\left( x^p \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}}\, du \right) \right),$ where $f(x) = \Theta(F(x))$ means that $c F(x) \le f(x) \le C F(x)$ for some constants $0 < c \le C$ and all large $x$ .

Remarks

The number $p$ exists and is unique because $s \mapsto \sum a_i b_i^s$ is continuous and strictly decreasing, with limits $\infty$ and $0$ . The proof is by induction on $x$ : one guesses the bound with suitable constants and checks that the recurrence preserves it. The growth condition on $g$ is used to compare $g$ at $b_i x$ and at $x$ . The perturbations $h_i$ cover floors and ceilings, such as $T(\lceil x/2 \rceil)$ , which appear in real algorithms. Example: for $T(x) = T(x/3) + T(2x/3) + x$ , one has $p = 1$ since $1/3 + 2/3 = 1$ , and $\int_1^x u/u^2\, du = \log x$ , so $T(x) = \Theta(x \log x)$ . The growth condition on $g$ is needed. For $T(x) = T(x/2) + 2^x$ , one has $p = 0$ , and the formula would give the order $2^x / x$ , since $\int_1^x 2^u u^{-1}\, du$ grows like $2^x/(x \log 2)$ ; but $T(x) \ge 2^x$ . Here $g(x) = 2^x$ fails the growth condition, as $g(x)/g(x/2) = 2^{x/2}$ is unbounded.

Going deeper

For a student

The theorem generalizes the master theorem of algorithm analysis, which handles only equal subproblem sizes $T(x) = a T(x/b) + g(x)$ . Here the pieces may have different sizes $b_i x$ , and small perturbations $h_i$ are allowed. To use it, first solve $\sum a_i b_i^p = 1$ for $p$ , then compute the integral of $g(u)/u^{p+1}$ . If $g(x) = x^q$ with $q < p$ , the integral stays bounded and $T = \Theta(x^p)$ ; if $q = p$ , one gets $\Theta(x^p \log x)$ ; if $q > p$ , one gets $\Theta(x^q)$ . In Mathlib a version is AkraBazziRecurrence.isTheta_asympBound.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`VZ1J7KM4QS`
URI	`m2://VZ1J7KM4QS`
Kind	statement, theorem
Writing	W0 stub
MSC	68W40, 39A22
Status	This copy of the site has no build data. Run `m2 status VZ1J7KM4QS`.
About	Recurrence relation
Uses	Big O notation, Recurrence relation