Akra-Bazzi method
In computer science, the Akra-Bazzi method is used to solve the mathematical recurrences that appear in the analysis of divide and conquer algorithms where the sub-problems have substantially different sizes. These recurrences are of the form
- <math>T(n) = \sum_{i=1}^k a_iT\left(\frac{n}{b_i}\right)+f(n)<math>
where k > 0, all coefficients ai are positive and sum to at least 1, all bi are greater than 1, and f(n) is bounded, positive and nondecreasing.
The method would work on a recurrence such as
- <math>T(n) = T(n/3) + T(2n/3) + O(n)<math>.
The Akra-Bazzi method generalizes the well-known Master theorem, which assumes that the sub-problems have equal size.
This article is a stub. You can help BambooWeb by .
