#The Akra-Bazzi method#

The [Akra-Bazzi method][1] 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)
$$

## Example##

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)
$$

(The help of [maxima][2] with the algebra is gratefully aknowledged)


  [1]: http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method
  [2]: http://maxima.sourceforge.net