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} = \sqrt n$$.

#### Recurrence 1

As $$f(n) = O(1) = O(n^{1/2 - 1/2})$$, case 1 of master method is applicable.

Hence, $$T(n) = \Theta(\sqrt n)$$

#### Recurrence 2

As $$f(n) = O(n^{1/2})$$, case 2 of master method is applicable.

Hence, $$T(n) = \Theta(\sqrt n \lg n)$$

#### Recurrence 3

As $$f(n) = O(n) = O(n^{1/2 + 1/2})$$, and $$2f(n/4) = n/2 \leq cn$$ for $$1/2 \leq c < 1$$ and sufficiently large $$n$$, case 3 of master is applicable.

Hence, $$T(n) = \Theta(n)$$

#### Recurrence 4

As $$f(n) = O(n^2) = O(n^{1/2 + 3/2})$$, and $$2f(n/4) = n^2/8 \leq cn^2$$ for $$1/8 \leq c < 1$$ and sufficiently large $$n$$, case 3 of master is applicable.

Hence, $$T(n) = \Theta(n^2)$$