The tight asymptotic bound for the recurrence T(n) = 2T(n/4) + √n is

Apply the Master Theorem to T(n) = 2T(n/4) + √n.

• Step 1: Identify parameters: a = 2, b = 4, and f(n) = √n = n^{1/2}.

• Step 2: Compute the critical exponent: n^{log_b a} = n^{log_4 2} = n^{1/2} = √n.

• Step 3: Compare f(n) to n^{log_b a}: f(n) = Θ(n^{1/2}) = Θ(n^{log_b a}), so this matches the balanced case of the Master Theorem (k = 0).

• Step 4: Apply the Master Theorem case 2: When f(n) = Θ(n^{log_b a} log^k n) with k = 0, the solution is T(n) = Θ(n^{log_b a} log^{k+1} n) = Θ(√n log n).

Answer: T(n) = Θ(√n log n).