The tight asymptotic bound for the recurrence: $T(n) = 2T(n/4) + \sqrt{n}$

We use the Master Theorem for $T(n) = aT(n/b) + f(n)$ Here, $a = 2$, $b = 4$, so $n^{\log_b a} = n^{\log_4 2} = n^{1/2} = \sqrt{n}$ Thus, $f(n) = \sqrt{n}$ is of the same order as $n^{\log_b a}$. Therefore, by Case 2 of Master Theorem, $T(n) = \Theta(n^{\log_b a} \log n) = \Theta(\sqrt{n} \log n)$ ✅ But wait! Let’s check growth dominance carefully: Actually, when $f(n) = \Theta(n^{\log_b a})$, we multiply by $\log n$, hence the correct bound is $\boxed{T(n) = \Theta(\sqrt{n} \log n)}$