57. State the master theorem and use it to solve T(n) = 3T(n/2) + n, T(n) = T(n/2) + 1 and T(n) = 2T(n/2) + n log n.
MediumAlgorithm analysis
Show model answer
For T(n) = aT(n/b) + f(n) with a >= 1 and b > 1, compare f(n) with n^(log_b a), the total work done at the leaves. If f(n) is polynomially smaller, the leaves dominate and T(n) = Θ(n^(log_b a)). If f(n) = Θ(n^(log_b a) · log^k n) with k >= 0, every level contributes about the same and T(n) = Θ(n^(log_b a) · log^(k+1) n). If f(n) is polynomially larger and satisfies the regularity condition a·f(n/b) <= c·f(n) for some c < 1, the root dominates and T(n) = Θ(f(n)).
T(n) = 3T(n/2) + n: log_2 3 ≈ 1.585, and n is polynomially smaller, so T(n) = Θ(n^1.585). T(n) = T(n/2) + 1: log_2 1 = 0, so n^0 = 1 matches f(n) with k = 0, giving Θ(log n) (binary search). T(n) = 2T(n/2) + n log n: n^(log_2 2) = n, and f(n) = n log n is the extended case 2 with k = 1, giving Θ(n log² n). The basic three-case version does not cover this one because n log n is larger than n but not polynomially larger.
What interviewers listen for
- Compare f(n) against n^(log_b a)
- Extended case 2 handles extra log factors
- Check regularity in case 3