Solution

The correct answer is Θ( √n · log n )

Key Points

• Given recurrence: T(n) = 2T(n/4) + √n.
• Compare with Master Theorem form: T(n) = aT(n/b) + f(n) where a = 2, b = 4, f(n) = n^1/2.
• Compute the critical exponent: n^log_ba = n^log₄2 = n^1/2.
• Since f(n) = Θ(n^log_ba), Master Theorem Case 2 applies.
• Therefore, T(n) = Θ(n^log_ba · log n) = Θ(√n · log n).

Important Points

• Case 1: If f(n) = O(n^{log_ba − ε}) ⇒ T(n) = Θ(n^log_ba).
• Case 2: If f(n) = Θ(n^log_ba) ⇒ T(n) = Θ(n^log_ba log n) (this problem).
• Case 3: If f(n) = Ω(n^{log_ba + ε}) and regularity holds ⇒ T(n) = Θ(f(n)).