Akra–Bazzi method

In computer science, the Akra - Bazzi theorem, or even the Akra - Bazzi method serves to determine the asymptotic behavior of solutions of mathematical recursion equations that arise in particular in the asymptotic analysis of divide-and -conquer algorithms. It was released in 1998 and is a generalization of the master theorem, which can be applied only to those who divide-and -conquer algorithms whose subproblems are of equal size.

Mathematical formulation

Consider the recurrence equation

For a function, such that the following conditions are met:

  • There are enough cases available basis, so that the equation has a unique solution;
  • And are constant for all i, with and;
  • , Where c is a constant, and O denotes the Landau - symbol;
  • For all i;
  • Is a constant.

Then, for the asymptotic behavior of T ( x) is the estimation of theta notation

With, so that

Intuitively, a small perturbation of the argument of T. ways and there is always between 0 and 1, can be used to ignore the integer function ( " floor function " ) in the argument. Similarly, one can argue for the irrelevance of the ceiling function ( " ceiling function " ) for the asymptotic behavior of T. For example, and according to the Akra - Bazzi theorem the same asymptotic behavior.

Examples

Mergesort

For mergesort the required number T (n) comparisons, which is approximately proportional to the duration given by the recurrence

With the base case. Thus, the Akra - Bazzi theorem can be applied, which with and k = 2, first p = 1, and thus the asymptotic behavior

Results.

Divide -and-conquer with unequal sub-problems

Be defined as one for all generations. According to the Akra - Bazzi method the value of p is calculated in the first step so that. The results here p = 2 In the second step, the asymptotic behavior is calculated according to the formula:

Importance

The Akra - Bazzi theorem covers a very wide class of recurrence equations and generalized considerably previously known results for the determination of asymptotic behavior. Mostly it is used for the Complexity recursive algorithms, in particular of a divide-and -conquer algorithms.

Swell

  • Mohamad Akra, Louay Bazzi: On the solution of linear recurrence equations. Computational Optimization and Applications 10 (2 ), 1998, pp. 195-210.
  • Tom Leighton: Notes on Better Master Theorem for Divide -and- Conquer Recurrences, Manuscript. Massachusetts Institute of Technology, 1996.
  • Recursion
  • Complexity Theory
Run time (program lifecycle phase)
38785
de