4.5 The master method for solving recurrences
4.5-1
a
Here, we have a = 2, b = 4, and $f(n) = \Theta(1)$, and thus we have that $n^{\log_ba} = n^{\log_4{2}} = n^{\frac{1}{2}}$. Since $n^{\frac{1}{2}}$ is polynomially larger than f(n) (that is, $f(n) = O(n^{\frac{1}{2} - \epsilon})$ for $\epsilon \leq \frac{1}{2}$), case 1 applies, and $T(n) = \Theta(n^{\frac{1}{2}})$.
b
Here, we have a = 2, b = 4, and $f(n) = \Theta(\sqrt{n})$, and thus we have that $n^{\log_ba} = n^{\log_4{2}} = n^{\frac{1}{2}}$. Case 2 applies, so $T(n) = \Theta(\sqrt{n}\lg{n})$.
c
Here, we have a = 2, b = 4, and $f(n) = \Theta(n)$, and thus we have that $n^{\log_ba} = n^{\log_4{2}} = n^{\frac{1}{2}}$. Since $f(n) = \Omega(n^{\frac{1}{2} + \epsilon})$, for $\epsilon \leq \frac{1}{2}$. Case 3 applies if we can show that the regularity condition holds for f(n). For sufficiently large n, we have that $af(\frac{n}{b}) = 2f(\frac{n}{4}) = 2\frac{n}{4} = \frac{n}{2} \leq cf(n)$ for $c = \frac{2}{3}$. So $T(n) = \Theta(n)$.
d
Here, we have a = 2, b = 4, and $f(n) = \Theta(n^2)$, and thus we have that $n^{\log_ba} = n^{\log_4{2}} = n^{\frac{1}{2}}$. Since $f(n) = \Omega(n^{\frac{1}{2} + \epsilon})$, for $\epsilon \leq \frac{3}{2}$. Case 3 applies if we can show that the regularity condition holds for f(n). For sufficiently large n, we have that $af(\frac{n}{b}) = 2f(\frac{n}{4}) = 2\frac{n}{4} = \frac{n}{2} \leq cf(n)$ for $c = \frac{1}{2}$. So $T(n) = \Theta(n^2)$.
4.5-2
In Strassen's algorithm, $T(n) = \Theta(n^{\lg7})$. In Professor Caesar's algorithm, $T(n) = aT(\frac{n}{4}) + \Theta(n^2)$. In order to beat Strassen's algorithm, then Professor Caesar's algorithm cannot apply case 3, since $f(n) = \Theta(n^2)$ which is polynomially larger than $\Theta(n^{\lg7})$.
We have that $n^{\log_ba} = n^{\log_4a} = n^{\frac{\lg{a}}{2}}$. If case 2 applies, then $f(n) = \Theta(n^{\frac{\lg{a}}{2}})$, so $n^{\frac{\lg{a}}{2}} = n^2$, a = 16. And $T(n) = \Theta(n^{\frac{\lg{a}}{2}}\lg{n}) = \Theta(n^2\lg{n})$ which cannot beat Strassen's algorithm.
So case 1 applies. And $T(n) = \Theta(n^{\frac{\lg{a}}{2}})$, and we have $\frac{\lg{a}}{2} < \lg7$, thus $a < 49$, so the largest integer value of a is 48.
4.5-3
Here, we have a = 1, b = 2, and $f(n) = \Theta(1)$, and thus we have that $n^{\log_ba} = n^{\log_2{1}} = 1$. Case 2 applies, so $T(n) = \Theta(n^{\log_ba}\lg{n}) = \Theta(\lg{n})$.
4.5-4
Here, we have a = 4, b = 2, and $f(n) = \Theta(n^2\lg{n})$, and thus we have that $n^{\log_ba} = n^{\log_2{4}} = n^2$. Since f(n) is not polymonially larger than $n^2$, so we cannot use master method to solve the recurrence.
According to exercise 4.6-2, $f(n) = \Theta(n^2\lg{n}) = \Theta(n^{\log_b{a}}\lg^k{n})$, where k = 1. So $T(n) = \Theta(n^{\log_b{a}}\lg^{k + 1}{n}) = \Theta(n^2\lg^2{n}) = \Theta((n\lg{n})^2)$.