To solve the recurrence relation T(n) = 2T(n/4) + \sqrt{n}, we need to find the tight asymptotic bound using the Master Theorem, which is commonly used for recurrences of the form:

T(n) = aT(n/b) + f(n)

In this case, the values are:

• a = 2
• b = 4
• f(n) = \sqrt{n}

The Master Theorem provides a way to determine asymptotic bounds based on f(n) compared to n^{\log_b{a}}.

Step 1: Compare f(n) with n^{\log_b{a}}.

First, calculate \log_b{a}:

\log_b{a} = \log_4{2}. We can further compute it as:

\log_4{2} = \frac{\log_2{2}}{\log_2{4}} = \frac{1}{2}

Therefore, n^{\log_b{a}} = n^{1/2}.

So, we now compare f(n) = \sqrt{n} with n^{1/2}.

\sqrt{n} = n^{1/2}, indicating the two functions are asymptotically equivalent.

Step 2: Apply the Third Case of the Master Theorem

Since f(n) = \Theta(n^{\log_b{a}}), by the Master Theorem, the solution to the recurrence is:

T(n) = \Theta(n^{\log_b{a}} \log n) = \Theta(n^{1/2} \log n) = \Theta(\sqrt{n} \log n)

Conclusion: The tight asymptotic bound for the recurrence relation T(n)= 2T(n/4) + \sqrt{n} is \Theta (\sqrt{n} \log n).