Answer to Question 1.10

Question. To within a constant factor, what is a solution to recurrence T(n) = 4T(n/2) + n²?

Answer. Here, a = 2, b = 4, log_b(a) = 2 and f(n) = n². Since f(n) is Θ(n²), this falls under the second case of the Master Theorem. The solution is T(n) = Θ(n²lg(n)).