#The Akra-Bazzi method#
The Akra-Bazzi method gives asymptotics for recurrences of the form: $$ T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for $x \ge x_0$} $$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $h_i(x)$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:
- There are enough base cases to get the recurrence going
- The $a_i$ and $b_i$ are all constants
- For all $i$, $a_i > 0$
- For all $i$, $0 < b_i < 1$
- $\lvert g(x) \rvert = O(x^c)$ for some constant $c$ as $x \rightarrow \infty$
- For all $i$, $\lvert h_i(x) \rvert = O(x / (\log x)^2)$
- $x_0$ is a constant
Note that $\lfloor b_i x \rfloor = b_i x - \{b_i x\}$, and as the sawtooth function $\{ u \} = u - \lfloor u \rfloor$ is always between 0 and 1, replacing $\lfloor b_i x \rfloor$ (or $\lceil b_i x \rceil$ as appropiate) satisfies the conditions on the $h_i$.
Find $p$ such that: $$ \sum_{1 \le i \le k} a_i b_i^p = 1 $$ Then the asymptotic behaviour of $T(x)$ as $x \rightarrow \infty$ is given by: $$ T(x) = \Theta \left( x^p \left( 1 + \int _1^x \frac{g(u)}{u^{p + 1}} du \right) \right) $$$$ T(x) = \Theta \left( x^p \left( 1 + \int_{x_1}^x \frac{g(u)}{u^{p + 1}} du \right) \right) $$ with $x_1$ "large enough", i.e. there is $k_1>0$ so that $$g(x/2) \geq k_1g(x) \tag{2}$$ for all $x>x_1$.
Examples##Example A
As an example, take the recursion for $n \ge 5$, where $T(0) = T(1) = T(2) = T(3) = T(4) = 17$: $$ T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n $$ The conditions are satisfied, we need $p$: $$ 9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1 $$ As luck would have it, $p = 2$. Thus we have: $$ T(n) = \Theta \left( n^2 \left(1 + \int_1^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$$$ T(n) = \Theta \left( n^2 \left(1 + \int_3^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$
since with $k_1 \leq \frac{1}{2}\left(1 - \frac{\log 2}{\log 3}\right)$ we fulfill $(2)$ for all $x\geq 3$. Note that because the integral converges even if we use other constants, such as $1$, as lower bound, it is legal to use those as well; the difference vanishes in $\Theta$.
Example B
Another example is the following for $n \ge 2$: $$ T(n) = 4 T(n / 2) + n^2 / \lg n $$ We have $g(n) = n^2 / \ln n = O(n^2)$, check. We have that there is a single $a_1 = 4$, $b_1 = 1 / 2$, which checks out. Assuming that the $n / 2$ is really $\lfloor n / 2 \rfloor$ and/or $\lceil n / 2 \rceil$, the implied $h_i(n)$ also check out. So we need: $$ a_1 b_1^p = 4 \cdot (1 / 2)^p = 1 $$ Thus $p = 2$, and: $$ T(n) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n) $$ (The integralWe apply a similar trick as given with lower limit 1 diverges, butabove to the lower limit should really bebound of the integral, only that we use $n$ for which the recurrence starts being valid; check$2$ because the original paperintegral does not converge for $1$.)
(The help of maxima with the algebra is gratefully acknowledged)
