Fock space

2014-01-08T10:37:45Z

193.136.24.142: /* Definition */

{{no footnotes|date=February 2013}}
In [[computer science]], the '''Akra–Bazzi method''', or '''Akra–Bazzi theorem''', is used to analyze the asymptotic behavior of the mathematical [[recurrence relation|recurrences]] that appear in the analysis of [[divide and conquer algorithm|divide and conquer]] [[algorithm]]s 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.

== 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))\qquad \text{for }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 O(x^c)</math>, where ''c'' is a constant and ''O'' notates [[Big O notation]]
* <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(x) 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 \Theta \left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}du \right)\right)</math>

(see [[Big O notation|Θ]]). 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.

== 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>
\begin{align}
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).
\end{align}
</math>

== 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 [[Run time (program lifecycle phase)|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>.

== References ==
*Mohamad Akra, Louay Bazzi: On the solution of linear recurrence equations. ''Computational Optimization and Applications'' '''10'''(2):195–210, 1998.
*Tom Leighton: [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.1636 Notes on Better Master Theorems for Divide-and-Conquer Recurrences], Manuscript. Massachusetts Institute of Technology, 1996, 9 pages.
*[http://www.mpi-inf.mpg.de/~mehlhorn/DatAlg2008/NewMasterTheorem.pdf Proof and application on few examples]

{{DEFAULTSORT:Akra-Bazzi Method}}
[[Category:Asymptotic analysis]]
[[Category:Theorems in discrete mathematics]]
[[Category:Recurrence relations]]
[[Category:Bazzi family]]

formulasearchengine - User contributions [en]

Fock space