Answer to Question 1.9

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

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