Answer to Question 1.7

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

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