View source for Akra–Bazzi method

{{short description|Method in computer science}}
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 algorithms|analysis]] of [[Divide-and-conquer algorithm|divide and conquer algorithms]] where the sub-problems have substantially different  sizes. It is a generalization of the [[master theorem (analysis of algorithms)|master theorem for divide-and-conquer recurrences]], which assumes that the sub-problems have equal size. It is named after mathematicians Mohamad Akra and Louay Bazzi.<ref name=":0" />

== Formulation ==
The Akra–Bazzi method applies to recurrence formulas of the form:<ref name=":0">{{Cite journal|last1=Akra|first1=Mohamad|last2=Bazzi|first2=Louay|date=May 1998|title=On the solution of linear recurrence equations|journal=Computational Optimization and Applications|volume=10|issue=2|pages=195–210|doi=10.1023/A:1018373005182|s2cid=7110614 }}</ref>

:<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 <math>i</math>
* <math>a_i > 0</math> for all <math>i</math>
* <math>0 < b_i < 1</math> for all <math>i</math>
* <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 <math>i</math>
* <math>x_0</math> is a constant

The asymptotic behavior of <math>T(x)</math> is found by determining the value of <math>p</math> for which <math>\sum_{i=1}^k a_i b_i^p = 1</math> and plugging that value into the equation:<ref>{{Cite web|url=https://people.mpi-inf.mpg.de/~mehlhorn/DatAlg2008/NewMasterTheorem.pdf|title=Proof and application on few examples}}</ref>

:<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 <math>T</math>.  By noting that <math>\lfloor b_i x \rfloor = b_i x + (\lfloor b_i x \rfloor - b_i x)</math> and that the absolute value of <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.

== 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 <math>p</math> for which <math>\frac{7}{4} \left(\frac{1}{2}\right)^p + \left(\frac{3}{4} \right)^p = 1</math>.  In this example, <math>p=2</math>.  Then, using the formula, the asymptotic behavior can be determined as follows:<ref>{{Cite book|title=Introduction to Algorithms|last1=Cormen|first1=Thomas|last2=Leiserson|first2=Charles|last3=Rivest|first3=Ronald|last4=Stein|first4=Clifford|publisher=MIT Press|year=2009|isbn=978-0262033848}}</ref>

:<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 running time 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>.

==See also==
* [[Master theorem (analysis of algorithms)]]
* [[Asymptotic complexity]]

== References ==
<references />

== External links ==
* [https://www.blogcyberini.com/2017/07/metodo-de-akra-bazzi.html O Método de Akra-Bazzi na Resolução de Equações de Recorrência] {{in lang|pt}}

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