Main Page | See live article | Alphabetical index

Akra-Bazzi method

In computer science, the Akra-Bazzi Method is a form of divide and conquer which solves more general cases of recurrence. The method is used to solve recurrences that model division of the problem into substantially unequal sized subproblems, as opposed to the Master method, which only solves equal sized subproblems.

The Akra-Bazzi method works for recurrences that have the form:

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

.