Akra-Bazzi method

In computer science, the Akra-Bazzi method, or Akra-Bazzi theorem, is used to analyze the asymptotic behavior of the mathematical recurrences that appear in the analysis of divide and conquer algorithms where the sub-problems have substantially different sizes. It is a generalization of the well-known Master theorem, which assumes that the sub-problems have equal size; that is, that the recursive expression for the desired function contains exactly one reference to the function.

The formula

The Akra-Bazzi method applies to recurrence formulas of the form

:$T(x)=g(x)\; +\; sum\_\{i=1\}^k\; a\_i\; T(b\_i\; x\; +\; h\_i(x))$ for $x\; geq\; x\_0.$

The conditions for usage are:

* sufficient base cases are provided
* $a\_i$ and $b\_i$ are constants for all i
* $a\_i\; >\; 0$ for all i
* for all i
* $left|g\text{'}(x)\; ight|\; in$O$(x^c)$, where "c" is a constant
* $left|\; h\_i(x)\; ight|\; in\; Oleft(frac\{x\}\{(log\; x)^2\}\; ight)$ for all i
* $x\_0$ is a constant

The asymptotic behavior of T(x) is found by determining the value of p for which $sum\_\{i=1\}^k\; a\_i\; b\_i^p\; =\; 1$ and plugging that value into the equation

:$T(x)\; in$Θ$left(\; x^pleft(\; 1+int\_1^x\; frac\{g(u)\}\{u^\{p+1du\; ight)\; ight).$

Intuitively, $h\_i(x)$ represents a small perturbation in the index of T. By noting that $lfloor\; b\_i\; x\; floor\; =\; b\_i\; x\; +\; (lfloor\; b\_i\; x\; floor\; -\; b\_i\; x)$ and that $lfloor\; b\_i\; x\; floor\; -\; b\_i\; x$ is always between 0 and 1, $h\_i(x)$ can be used to ignore the floor function in the index. Similarly, one can also ignore the ceiling function. For example, $T(n)\; =\; n\; +\; T\; left(frac\{1\}\{2\}\; n\; ight)$ and $T(n)\; =\; n\; +\; T\; left(leftlfloor\; frac\{1\}\{2\}\; n\; ight\; floor\; ight)$ will, as per the Akra-Bazzi theorem, have the same asymptotic behavior.

An example

Suppose $T(n)$ is defined as 1 for integers $0\; leq\; n\; leq\; 3$ and $n^2\; +\; frac\{7\}\{4\}\; T\; left(\; leftlfloor\; frac\{1\}\{2\}\; n\; ight\; floor\; ight)\; +\; T\; left(\; leftlceil\; frac\{3\}\{4\}\; n\; ight\; ceil\; ight)$ for integers $n\; >\; 3$. In applying the Akra-Bazzi method, the first step is to find the value of p for which $frac\{7\}\{4\}\; left(frac\{1\}\{2\}\; ight)^p\; +\; left(frac\{3\}\{4\}\; ight)^p\; =\; 1$. In this example, "p" = 2. Then, using the formula, the asymptotic behavior can be determined as follows:

:$T(x)\; in\; Theta\; left(\; x^pleft(\; 1+int\_1^x\; frac\{g(u)\}\{u^\{p+1,du\; ight)\; ight)$

::$=Theta\; left(\; x^2\; left(\; 1+int\_1^x\; frac\{u^2\}\{u^3\},du\; ight)\; ight)$

::$=Theta(x^2(1\; +\; ln\; x)),$

::$=Theta(x^2\; log\; x).,$

Significance

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 runtime 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 $T(1)\; =\; 0$ and

:$T(n)\; =\; Tleft(leftlfloor\; frac\{1\}\{2\}\; n\; ight\; floor\; ight)\; +\; Tleft(leftlceil\; frac\{1\}\{2\}\; n\; ight\; ceil\; ight)\; +\; n\; -\; 1$

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

References

*Mohamad Akra, Louay Bazzi: On the solution of linear recurrence equations. Computational Optimization and Applications 10(2), 1998, pp. 195-210 .
*Tom Leighton: [http://citeseer.ist.psu.edu/252350.html Notes on Better Master Theorems for Divide-and-Conquer Recurrences] , Manuscript. Massachusetts Institute of Technology, 1996, 9 pages.