# The Master Method

For the recurrence

*T*(*n*) = 3*T*(*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*) = Θ(*n*lg *n*).

The master method does not apply to the recurrence

*T*(*n*) = 2*T*(*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.