A divide-and-conquer algorithm solves a problem by dividing it into smaller subproblems of the same type, solving the subproblems by recursion
until reaching directly solvable base cases, and combining their solutions. Its running
time is therefore often described by a recurrence
equation. If a problem of size 
is divided into 
subproblems of size 
and the division and combination require time 
, a typical recurrence
equation is
 |
The Akra-Bazzi method treats a more general class in which the subproblems can have unequal sizes and their arguments can contain controlled perturbations.
