Akra-Bazzi theorem

In computer science , the Akra-Bazzi theorem , or the Akra-Bazzi method , is used to determine the asymptotic behavior of solutions to mathematical recursion equations that occur in the asymptotic analysis of divide-and-conquer algorithms in particular . It was published in 1998 and is a generalization of the master theorem that can only be applied to divide-and-conquer algorithms whose sub-problems are of the same size.

Mathematical formulation

The recursion equation is given

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

for a function so that the following conditions are met: ${\displaystyle T:\mathbb {R} ^{+}\to \mathbb {R} ^{+}}$

• There are enough base cases so that the equation can be solved uniquely;
• ${\displaystyle a_{i}}$and are constant for all i , with and ; ${\displaystyle b_{i}}$ ${\displaystyle a_{i}>0}$ ${\displaystyle 0<b_{i}<1}$
• ${\displaystyle \left|g'(x)\right|\in O\left(x^{c}\right)}$, where c is a constant and O denotes the Landau symbol ;
• ${\displaystyle \left|h_{i}(x)\right|\in O\left({\frac {x}{(\log x)^{2}}}\right)}$for all i ;
• ${\displaystyle x_{0}}$ is a constant.

Then for the asymptotic behavior of T ( x ) the estimate in the theta notation applies

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

with so that ${\displaystyle p\in \mathbb {R} ^{+}}$ ${\displaystyle \sum _{i=1}^{k}a_{i}b_{i}^{p}=1.}$

A small perturbation of T's argument is intuitive . Because and because is always between 0 and 1 , the Gaussian brackets ("floor function") in the argument can be ignored. Similarly, one can argue for the irrelevance of the rounding function ("ceiling function") for the asymptotic behavior of T. For example, and according to the Akra-Bazzi theorem have the same asymptotic behavior. ${\displaystyle h_{i}(x)}$ ${\displaystyle \lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)}$ ${\displaystyle \lfloor b_{i}x\rfloor -b_{i}x}$ ${\displaystyle h_{i}(x)}$ ${\displaystyle T(n)=n+T\left({\frac {1}{2}}n\right)}$ ${\displaystyle T(n)=n+T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)}$

Examples

Merge sort

For the merge sort , the required number T ( n ) of comparisons, which is approximately proportional to its running time, is given by the recursion equation

${\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}$

with the base case . Thus the Akra-Bazzi theorem can be applied, which with and k = 2 ,, initially p = 1 and thus the asymptotic behavior ${\displaystyle T(1)=0}$ ${\displaystyle g(u)=u+1}$ ${\displaystyle a_{1}=a_{2}=1,}$ ${\displaystyle b_{1}=b_{2}=1/2}$

${\displaystyle T(n)\in \Theta \left(n\left(1+\int _{1}^{n}{\frac {u+1}{u^{2}}}\,\mathrm {d} u\right)\right)=\Theta \left(n\left(\ln n+{\frac {1}{n}}\right)\right)=\Theta (n\,\log n)}$

results.

Divide-and-conquer with unequal sub-problems

Be defined as one for and for . According to the Akra-Bazzi method, the first step is to calculate the value of p such that . This results in p = 2. In the second step, the asymptotic behavior is calculated using the formula: ${\displaystyle T(n)}$ ${\displaystyle 0\leq n\leq 3}$ ${\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)}$ ${\displaystyle n>3}$ ${\displaystyle {\frac {7}{4}}\left({\frac {1}{2}}\right)^{p}+\left({\frac {3}{4}}\right)^{p}=1}$

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

meaning

The Akra-Bazzi theorem encompasses a very broad class of recursion equations and generalizes theorems that were previously known to determine asymptotic behavior. It is mainly used to consider the complexity of recursive algorithms, especially divide-and-conquer algorithms.

swell

• Mohamad Akra, Louay Bazzi: On the solution of linear recurrence equations. Computational Optimization and Applications 10 (2), 1998, pp. 195-210.

• Tom Leighton: Notes on Better Master Theorems for Divide-and-Conquer Recurrences , Manuscript. Massachusetts Institute of Technology, 1996.