Recurrences Where the Master Theorem Cannot Be Applied

The Master Theorem cannot be used if the recurrence does not fit the standard form.

Examples:

Different-sized subproblems

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

Not applicable because the recursive calls are of different sizes.

---

Variable-size reduction

$$T(n)=T(n-1)+n$$

Not applicable because the problem size is reduced by subtraction rather than division.

---

Non-standard recurrence

$$T(n)=T(\sqrt n)+1$$

Not applicable because the subproblem size is $\sqrt n$, not $n/b$

Such recurrences require methods like substitution, recursion trees, or more advanced techniques (e.g., the Akra–Bazzi theorem).

Functions Cannot Be Compared

If the driving function and the watershed function are not asymptotically comparable, the theorem cannot be used.

Gap Between Cases

There is a gap between Cases 1 and 2 and also between Cases 2 and 3.

For example,

$$T(n)=2T(n/2)+\frac{n}{\log n}$$

Here,

• watershed $=n$
  
• driving function $=n/\log n$
  

Although $n/\log n=o(n)$, it is not polynomially smaller than $n$, so Case 1 does not apply.

It also does not fit Case 2 because Case 2 requires $\log^k n$ with $k\ge \mathrm{0,\; whereas\; here }$$k=-1$.

Hence the Master Theorem cannot solve this recurrence. Other techniques such as the substitution method or the Akra–Bazzi method are required