Answer to Question 1.8

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

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