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

a. \(T(n) = 2T(n/4) + 1\)

\(a = 2\), \(b = 4\) and \(f(n) = 1\).

Case 1 applies since \(f(n) = O(n^{\log_{4}2-\epsilon}) = O(n^{\frac{1}{2} - \frac{1}{2}})\), and thus the solution to the recurrence is \(T(n) = \Theta(n^{\log_{4}2}) = \Theta(\sqrt{n})\).

b. \(T(n) = 2T(n/4) + \sqrt{n}\)

\(a = 2\), \(b = 4\) and \(f(n) = \sqrt{n}\).

Case 1 does not apply since \(f(n) = O(n^{\log_{4}2-\epsilon}) \implies \epsilon = 0\).

Case 2 applies since \(f(n) = \Theta(n^{\log_{4}2}) = \Theta(n^{\frac{1}{2}})\), and thus the solution to the recurrence is \(T(n) = \Theta(\sqrt{n} \lg n)\).

c. \(T(n) = 2T(n/4) + n\)

\(a = 2\), \(b = 4\) and \(f(n) = n\).

Case 1 does not apply since \(f(n) = O(n^{\log_{4}2 - \epsilon}) \implies \epsilon = - \frac{1}{2}\).

Case 2 does not apply since \(f(n) = \Theta(n^{\log_{4}2}) = \Theta(\sqrt{n})\) does not hold.

Case 3 applies since \(f(n) = \Omega(n^{\log_{4}2 + \epsilon}) = \Omega(n^{\frac{1}{2} + \frac{1}{2}})\) and

\[\begin{split} a(f(n/b)) & \leq cf(n) \\ 2(n/4) & \leq cn \\ \frac{1}{2}n & \leq cn \\ \end{split}\]

holds for \(\frac{1}{2} \leq c < 1\). Thus the solution to the recurrence is \(T(n) = \Theta(f(n)) = \Theta(n)\).

d. \(T(n) = 2T(n/4) + n^2\)

Case 1 does not apply since \(f(n) = O(n^{\log_{4}2 - \epsilon}) \implies \epsilon = -\frac{3}{2}\).

Case 2 does not apply since \(f(n) = \Theta(n^{\log_{4}2}) = \Theta(\sqrt{n})\) does not hold.

Case 3 applies since \(\Omega(n^{\log_{4}2 + \epsilon}) = \Omega(n^{\frac{1}{2} + \frac{3}{2}})\) and

\[\begin{split} a(f(n/b)) & \leq cf(n) \\ 2(n^2/4) & \leq cn^2 \\ \frac{1}{2}n^2 & \leq cn^2 \\ \end{split}\]

holds for \(\frac{1}{2} \leq c < 1\). Thus the solution to the recurrence is \(T(n) = \Theta(f(n)) = \Theta(n^2)\).