Akra-Bazzi method

From Free net 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

<math>T(x)=g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x))</math> for <math>x \geq x_0.</math>

The conditions for usage are:

  • sufficient base cases are provided
  • <math>a_i</math> and <math>b_i</math> are constants for all i
  • <math>a_i > 0</math> for all i
  • <math>0 < b_i < 1</math> for all i
  • <math>\left|g'(x)\right| \in</math>O<math>(x^c)</math>, where c is a constant
  • <math>\left| h_i(x) \right| \in O\left(\frac{x}{(\log x)^2}\right)</math> for all i
  • <math>x_0</math> is a constant

The asymptotic behavior of T(n) is found by determining the value of p for which <math>\sum_{i=1}^k a_i b_i^p = 1</math> and plugging that value into the equation

<math>T(x) \in </math>Θ<math>\left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}du \right)\right).</math>

Intuitively, <math>h_i(x)</math> represents a small perturbation in the index of T. By noting that <math>\lfloor b_i x \rfloor = b_i x + (\lfloor b_i x \rfloor - b_i x)</math> and that <math>\lfloor b_i x \rfloor - b_i x</math> is always between 0 and 1, <math>h_i(x)</math> can be used to ignore the floor function in the index. Similarly, one can also ignore the ceiling function. For example, <math>T(n) = n + T \left(\frac{1}{2} n \right)</math> and <math>T(n) = n + T \left(\left\lfloor \frac{1}{2} n \right\rfloor \right)</math> will, as per the Akra-Bazzi theorem, have the same asymptotic behavior.

[edit]

An example

Suppose <math>T(n)</math> is defined as 1 for integers <math>0 \leq n \leq 3</math> and <math>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)</math> for integers <math>n > 3</math>. In applying the Akra-Bazzi method, the first step is to find the value of p for which <math>\frac{7}{4} \left(\frac{1}{2}\right)^p + \left(\frac{3}{4} \right)^p = 1</math>. In this example, p = 2. Then, using the formula, the asymptotic behavior can be determined as follows:

<math>T(x) \in \Theta \left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}\,du \right)\right)</math>
<math>=\Theta \left( x^2 \left( 1+\int_1^x \frac{u^2}{u^3}\,du \right)\right)</math>
<math>=\Theta(x^2(1 + \ln x))\,</math>
<math>=\Theta(x^2 \log x).\,</math>
[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 <math>T(1) = 0</math> and

<math>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</math>

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

Retrieved from "http://www.netipedia.com/index.php/Akra-Bazzi_method"