In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied 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
Analysis (: analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
of
divide and conquer algorithms where the sub-problems have substantially different sizes. It is a generalization of the
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.
A practical variation sometimes referred to as the Ali Najib Variation is commonly used when the exact value of the exponent ''p'' satisfying the equation
is difficult to compute analytically.
Formulation
The Akra–Bazzi method applies to recurrence formulas of the form:
:
The conditions for usage are:
* sufficient base cases are provided
*
and
are constants for all
*
for all
*
for all
*
, where ''c'' is a constant and ''O'' notates
Big O notation
Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
*
for all
*
is a constant
The asymptotic behavior of
is found by determining the value of
for which
and plugging that value into the equation:
:
(see
Θ). Intuitively,
represents a small perturbation in the index of
. By noting that
and that the absolute value of
is always between 0 and 1,
can be used to ignore the
floor function
In mathematics, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or eq ...
in the index. Similarly, one can also ignore the
ceiling function
In mathematics, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or eq ...
. For example,
and
will, as per the Akra–Bazzi theorem, have the same asymptotic behavior.
Ali Najib variation
When directly solving
for the exponent p is inconvenient, the Ali Najib Variation offers a shortcut. Instead of determining p exactly, one compares the value of
to 1 for the exponent d appearing in the non-recursive term
:
If
, then
If
, then
If
, then
, where p is defined by
This comparison-based approach is particularly handy when p cannot be expressed in closed form or would require numerical methods.
Example
Suppose
is defined as 1 for integers
and
for integers
. In applying the Akra–Bazzi method, the first step is to find the value of
for which
. In this example,
. Then, using the formula, the asymptotic behavior can be determined as follows:
:
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
In computer science, merge sort (also commonly spelled as mergesort and as ) is an efficient, general-purpose, and comparison sort, comparison-based sorting algorithm. Most implementations of merge sort are Sorting algorithm#Stability, stable, wh ...
, the number of comparisons required in the worst case, which is roughly proportional to its runtime, is given recursively as
and
:
for integers
, and can thus be computed using the Akra–Bazzi method to be
.
See also
*
Master theorem (analysis of algorithms)
Master, master's or masters may refer to:
Ranks or titles
In education:
*Master (college), head of a college
*Master's degree, a postgraduate or sometimes undergraduate degree in the specified discipline
* Schoolmaster or master, presiding offic ...
*
Asymptotic complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
References
External links
O Método de Akra-Bazzi na Resolução de Equações de Recorrência
{{DEFAULTSORT:Akra-Bazzi Method
Asymptotic analysis
Theorems in discrete mathematics
Recurrence relations