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
* $$0 < b_i < 1 for all i
* $$left|g'(x) ight| inO$$(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.