# Akra-Bazzi method

Akra-Bazzi method

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.

The formula

The Akra-Bazzi method applies to recurrence formulas of the form

:$T\left(x\right)=g\left(x\right) + sum_\left\{i=1\right\}^k a_i T\left(b_i x + h_i\left(x\right)\right)$ 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\text{'}\left(x\right) ight| in$O$\left(x^c\right)$, where "c" is a constant
* $left| h_i\left(x\right) ight| in Oleft\left(frac\left\{x\right\}\left\{\left(log x\right)^2\right\} ight\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_\left\{i=1\right\}^k a_i b_i^p = 1$ and plugging that value into the equation

:$T\left(x\right) in$Θ$left\left( x^pleft\left( 1+int_1^x frac\left\{g\left(u\right)\right\}\left\{u^\left\{p+1du ight\right) ight\right).$

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

An example

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

:$T\left(x\right) in Theta left\left( x^pleft\left( 1+int_1^x frac\left\{g\left(u\right)\right\}\left\{u^\left\{p+1,du ight\right) ight\right)$

::$=Theta left\left( x^2 left\left( 1+int_1^x frac\left\{u^2\right\}\left\{u^3\right\},du ight\right) ight\right)$

::$=Theta\left(x^2\left(1 + ln x\right)\right),$

::$=Theta\left(x^2 log x\right).,$

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\left(1\right) = 0$ and

:$T\left(n\right) = Tleft\left(leftlfloor frac\left\{1\right\}\left\{2\right\} n ight floor ight\right) + Tleft\left(leftlceil frac\left\{1\right\}\left\{2\right\} n ight ceil ight\right) + n - 1$

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

References

*Mohamad Akra, Louay Bazzi: On the solution of linear recurrence equations. Computational Optimization and Applications 10(2), 1998, pp. 195-210 .
*Tom Leighton: [http://citeseer.ist.psu.edu/252350.html Notes on Better Master Theorems for Divide-and-Conquer Recurrences] , Manuscript. Massachusetts Institute of Technology, 1996, 9 pages.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Master-Method — Der Begriff Hauptsatz der Laufzeitfunktionen oder oft englisch Master Theorem, das ein Spezialfall des Akra Bazzi Theorems ist, bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt …   Deutsch Wikipedia

• Master Method — Der Begriff Hauptsatz der Laufzeitfunktionen oder oft englisch Master Theorem, das ein Spezialfall des Akra Bazzi Theorems ist, bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt …   Deutsch Wikipedia

• Master theorem — For a result in enumerative combinatorics, see MacMahon Master theorem. In the analysis of algorithms, the master theorem provides a cookbook solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the… …   Wikipedia

• List of mathematics-based methods — This is a list of mathematics based methods, by Wikipedia page.See also list of graphical methods.*Adams method (differential equations) *Akra Bazzi method (asymptotic analysis) *Condorcet method (voting systems) *Coombs method (voting systems)… …   Wikipedia

• List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

• Divide and conquer algorithm — In computer science, divide and conquer (D C) is an important algorithm design paradigm based on multi branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub problems of the same (or… …   Wikipedia

• List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

• Outline of combinatorics — See also: Index of combinatorics articles The following outline is presented as an overview of and topical guide to combinatorics: Combinatorics – branch of mathematics concerning the study of finite or countable discrete structures. Contents 1… …   Wikipedia