Akra-Bazzi

Mohamad Akra and Louay Bazzi. On the solution of linear recurrence equations. Computational Optimization and Applications, 10(2):1953210, 1998.

https://link.springer.com/article/10.1023/A:1018373005182

Recurrences

Akra-Bazzi recurrence takes the form

$$T(n)=f(n)+\sum _{i=1}^k{a}_{i}T(n/b_i)$$

where $k$ is positive integer, $a_i$ is strictly positive, $b_i$ strictly greater than $1$, $f(n)$ non-negative and defined on large $n$.

Akra-Bazzi recurrences generalize on master-theorem, as problems can be divided into different-sized subproblems.

• The driving function must satisfy polynomial-growth condition.
  • Functions in form of $f(n)=\Theta \left(n^{\alpha }{\lg }^{\beta }n\lg {\lg }^{\gamma }n\right)$ satisfy it.
  • Loosely speaking, we need $f(\Theta (n))=\Theta (f(n))$, though the condition is actually stronger.
  • In such case, the floors and ceilings can be ignored.
• Replacing $T(n/b_i)$ with either $T(\lceil n/b_i\rceil )$ or $T(\lfloor n/b_i\rfloor )$ does not affect the asymptotic solution, in fact, much larger perturbation is allowed.

Method

Determine a unique $p$ (due to monotonicity), so that

$$\sum _{i=1}^k{a}_i/b_i^p=1$$

Then the solution is

$$T(n)=\Theta \left(n^p\left(1+{\int }_1^n\frac{f(x)}{x^{p+1}}\mathrm{d}x\right)\right)$$