Akra–Bazzi method

The Akra–Bazzi method applies to recurrence formulas of the form[1]

${\displaystyle T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))\qquad {\text{for }}x\geq x_{0}.}$

The conditions for usage are:

• sufficient base cases are provided
• ${\displaystyle a_{i}}$ and ${\displaystyle b_{i}}$ are constants for all ${\displaystyle i}$
• ${\displaystyle a_{i}>0}$ for all ${\displaystyle i}$
• ${\displaystyle 0<b_{i}<1}$ for all ${\displaystyle i}$
• ${\displaystyle \left|g(x)\right|\in O(x^{c})}$, where c is a constant and O notates Big O notation
• ${\displaystyle \left|h_{i}(x)\right|\in O\left({\frac {x}{(\log x)^{2}}}\right)}$ for all ${\displaystyle i}$
• ${\displaystyle x_{0}}$ is a constant

The asymptotic behavior of ${\displaystyle T(x)}$ is found by determining the value of ${\displaystyle p}$ for which ${\displaystyle \sum _{i=1}^{k}a_{i}b_{i}^{p}=1}$ and plugging that value into the equation[2]

${\displaystyle T(x)\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}du\right)\right)}$

(see Θ). Intuitively, ${\displaystyle h_{i}(x)}$ represents a small perturbation in the index of ${\displaystyle T}$. By noting that ${\displaystyle \lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)}$ and that the absolute value of ${\displaystyle \lfloor b_{i}x\rfloor -b_{i}x}$ is always between 0 and 1, ${\displaystyle h_{i}(x)}$ can be used to ignore the floor function in the index. Similarly, one can also ignore the ceiling function. For example, ${\displaystyle T(n)=n+T\left({\frac {1}{2}}n\right)}$ and ${\displaystyle T(n)=n+T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)}$ will, as per the Akra–Bazzi theorem, have the same asymptotic behavior.

Suppose ${\displaystyle T(n)}$ is defined as 1 for integers ${\displaystyle 0\leq n\leq 3}$ and ${\displaystyle n^{2}+{\frac {7}{4}}T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)+T\left(\left\lceil {\frac {3}{4}}n\right\rceil \right)}$ for integers ${\displaystyle n>3}$. In applying the Akra–Bazzi method, the first step is to find the value of ${\displaystyle p}$ for which ${\displaystyle {\frac {7}{4}}\left({\frac {1}{2}}\right)^{p}+\left({\frac {3}{4}}\right)^{p}=1}$. In this example, ${\displaystyle p=2}$. Then, using the formula, the asymptotic behavior can be determined as follows:[3]

${\displaystyle {\begin{aligned}T(x)&\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}\,du\right)\right)\\&=\Theta \left(x^{2}\left(1+\int _{1}^{x}{\frac {u^{2}}{u^{3}}}\,du\right)\right)\\&=\Theta (x^{2}(1+\ln x))\\&=\Theta (x^{2}\log x).\end{aligned}}}$

The Akra–Bazzi method is more useful than most other techniques for determining asymptotic behavior because it covers such a wide variety of cases. Its primary application is the approximation of the running time of many divide-and-conquer algorithms. For example, in the merge sort, the number of comparisons required in the worst case, which is roughly proportional to its runtime, is given recursively as ${\displaystyle T(1)=0}$ and

${\displaystyle T(n)=T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)+T\left(\left\lceil {\frac {1}{2}}n\right\rceil \right)+n-1}$

for integers ${\displaystyle n>0}$, and can thus be computed using the Akra–Bazzi method to be ${\displaystyle \Theta (n\log n)}$.

• Master theorem (analysis of algorithms)
• Asymptotic complexity

• O Método de Akra-Bazzi na Resolução de Equações de Recorrência (in Portuguese)