Akra-Bazzi Method

The Akra-Bazzi method determines the asymptotic growth of running-time recurrence equations arising from divide-and-conquer algorithms. In one common form, the recurrence equation is

(1)

where , , the perturbations satisfy , and the function obeys the required regularity and polynomial-growth conditions. If is the unique real number satisfying

(2)

then

(3)

The method generalizes the equal-subproblem recurrence equation by allowing subproblems of unequal sizes and controlled perturbations of their arguments (Akra and Bazzi 1998).