Exercise 4.5.1

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$

1. $\Theta(n^{\log_4{2}}) = \Theta(\sqrt{n})$
2. $\Theta(n^{\log_4{2}}\lg{n}) = \Theta(\sqrt{n}\lg{n})$
3. $\Theta(n)$
4. $\Theta(n^2)$