|
Contents
Akra-Bazzi Method
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 substanially 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:
- <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>.
| Elsewhere |  | |
Search engine
Web directory
|
CONTENTS:
|
