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 a
i are positive and sum to at least 1, all b
i are greater than 1, and f(n) is bounded, positive and nondecreasing.
The method would work on a recurrence such as
- .