Akra–Bazzi Method 

Introduction

The Akra–Bazzi Method is a general technique for solving divide-and-conquer recurrences. It extends the Master Theorem and can solve many recurrences that the Master Theorem cannot.

The method was developed by Mohamad Akra and Louay Bazzi in 1998.

Unlike the Master Theorem, the Akra–Bazzi Method can handle recurrences in which:

• the subproblems are of different sizes,
• the recursive calls are unequal, and
• the problem sizes are not always reduced by the same factor.

Although the method involves some calculus, it provides asymptotically tight bounds for a much broader class of recurrence relations.

---

General Form

The Akra–Bazzi Method solves recurrences of the form

$$T(n)=\sum_{i=1}^{k}a_iT(b_in+h_i(n))+g(n)$$

where

• $a_i>\mathrm{0\; are\; constants,}$
• $0<b_i<\mathrm{1,}$
• $h_i(n)$ is a lower-order function,
• $g(n)$ is the non-recursive work.

---

When is it Used?

The Akra–Bazzi Method is particularly useful when the Master Theorem cannot be applied.

Example 1

$$T(n)=T(n/3)+T(2n/3)+n$$

The Master Theorem cannot solve this recurrence because the recursive calls have different sizes.

The Akra–Bazzi Method can solve it and gives

$$\boxed{T(n)=\Theta(n\log n)}$$

---

Example 2

$$T(n)=T(n/5)+T(7n/10)+n$$

Again, the recursive calls are unequal, so the Master Theorem does not apply. The Akra–Bazzi Method can be used to obtain the asymptotic running time.

---

Advantages

• More general than the Master Theorem.
• Solves recurrences with unequal-sized subproblems.
• Provides tight asymptotic bounds.
• Applicable to many practical divide-and-conquer algorithms.

---

Limitations

• Requires knowledge of calculus.
• More mathematically involved than the Master Theorem.
• Not usually covered in introductory undergraduate algorithm courses in detail.

---

Comparison with the Master Theorem

Master Theorem	Akra–Bazzi Method
Applies to recurrences of the form $T(n)=aT(n/b)+f(n)$	Applies to a much broader class of divide-and-conquer recurrences
Requires equal-sized subproblems	Allows unequal-sized subproblems
Easy to apply	More mathematically involved
No calculus required	Uses calculus and integral analysis
Limited applicability	More general and powerful

---

Summary

The Akra–Bazzi Method is a powerful extension of the Master Theorem for solving general divide-and-conquer recurrences. It is especially useful for recurrences with unequal subproblem sizes, where the Master Theorem fails. Although it involves calculus and is more advanced, it provides tight asymptotic bounds for a wide range of recursive algorithms.