# 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_iT(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-notation|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 dx \right) \right) $