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 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

<math>T(n) = T(n/3) + T(2n/3) + O(n)</math>.