Editing Akra–Bazzi method (section)

== 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.