Beyond the master theorem – the Akra-Bazzi method
In the previous section, we discussed the limitations of the master theorem in solving recurrence functions. Although the master theorem can address a wide range of problems and is the most common approach, it does have its constraints. For example, it only applies to a specific class of divide-and-conquer recurrence functions:
Here, the subproblem sizes are equal (
). As we showed in the previous section, we can solve special cases of subtracting recurrence functions using the master theorem. It also has limitations on the form of the function 
. Specifically, the master theorem struggles with the following:
- Unequal subproblem sizes: The recurrence splits into subproblems of significantly different sizes
- More complex splitting: There are more than two subproblems in the recursion
- Non-polynomial work: The function
representing the work done outside the recursive calls isn’t easily categorized as polynomial...
