For the recurrence
T(n) = 3T(n/4) n lg n,
we have a = 3, b = 4, f (n) = n lg n, and . Since
, where ∈≈ 0.2, case 3 applies if we can show that the regularity condition holds for f (n). For sufficiently large n, af (n/b) = 3(n/4)lg(n/4) ≤ (3/4)n lg n = cf (n) for c = 3/4. Consequently, by case 3, the solution to the recurrence is T(n) = Θ(nlg n).
The master method does not apply to the recurrence
T(n) = 2T(n/2) n lg n,
even though it has the proper form: a = 2, b = 2, f(n) = n lg n, and . It might seem that case 3 should apply, since f (n) = n lg n is asymptotically larger than . The problem is that it is not polynomially larger. The ratio is asymptotically less than n∈for any positive constant ∈. Consequently, the recurrence falls into the gap between case 2 and case 3.