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 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 extends the familiar equal-subproblem result for a divide-and-conquer algorithm by allowing unequal subproblem sizes and controlled perturbations of their arguments (Akra and Bazzi 1998).