Akra-Bazzi method

From Wikipedia, the free encyclopedia

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.

[edit] 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)\right| \in$ O $(x c)$ , where c is a constant
$\left| h_i(x) \right| \in O\left(\frac{x}{(\log x)^2}\right)$ 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^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}du \right)\right).$

Intuitively, $h i (x)$ represents a small perturbation in the index of T. By noting that $\lfloor b_i x \rfloor = b_i x + (\lfloor b_i x \rfloor - b_i x)$ and that $\lfloor b_i x \rfloor - 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 \right)$ and $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.

[edit] An example

Suppose $T (n)$ is defined as 1 for integers $0 \leq n \leq 3$ and $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 $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}\right)^p + \left(\frac{3}{4} \right)^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^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).\,$

[edit] 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) = T\left(\left\lfloor \frac{1}{2} n \right\rfloor \right) + T\left(\left\lceil \frac{1}{2} n \right\rceil \right) + n - 1$