SKEDSOFT

Design Analysis Of Algorithm

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 nfor any positive constant . Consequently, the recurrence falls into the gap between case 2 and case 3.