Use the master method to give tight asymptotic bounds for the following recurrences.

1. $T(n) = 2T(n/4) + 1$.
2. $T(n) = 2T(n/4) + \sqrt n$.
3. $T(n) = 2T(n/4) + n$.
4. $T(n) = 2T(n/4) + n^2$.

In all of the recurrences, $a = 2$ and $b = 4$. Hence, $n^{\log_b a} = n^{1/2}$.

Recurrence 1 : $f(n) = O(1) = O(n^{1/2 - 1/2}) \implies \text {case 1}$ Hence, $T(n) = \Theta(n^{1/2})$

Recurrence 2 : $f(n) = O(n^{1/2}) \implies \text {case 2}$ Hence, $T(n) = \Theta(n^{1/2} \lg n)$

Recurrence 3 : $f(n) = O(n) = O(n^{1/2 + 1/2}) \implies \text {case 3}$ Hence, $T(n) = \Theta(n)$

Recurrence 4 : $f(n) = O(n^2) = O(n^{1/2 + 3/2}) \implies \text {case 3}$ Hence, $T(n) = \Theta(n^2)$