Encyclopedia > Akra-Bazzi Method

  Article Content

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
BBC News 24

... viewers were able to view the service. The BBC were initially criticized for the cost of running BBC News 24 channel, with so few viewers. Their response was ...

 
 
 
This page was created in 33.5 ms