4.5 The master method for solving recurrences

4.5-1

a

Here, we have a = 2, b = 4, and $f(n)=\mathrm{\Theta }(1)$, and thus we have that $n^{{\log }_{b}a}=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}-ϵ})$ for $ϵ\le \frac{1}{2}$), case 1 applies, and $T(n)=\mathrm{\Theta }(n^{\frac{1}{2}})$.

b

Here, we have a = 2, b = 4, and $f(n)=\mathrm{\Theta }(\sqrt{n})$, and thus we have that $n^{{\log }_{b}a}=n^{{\log }_{4}2}=n^{\frac{1}{2}}$. Case 2 applies, so $T(n)=\mathrm{\Theta }(\sqrt{n}\lg n)$.

c

Here, we have a = 2, b = 4, and $f(n)=\mathrm{\Theta }(n)$, and thus we have that $n^{{\log }_{b}a}=n^{{\log }_{4}2}=n^{\frac{1}{2}}$. Since $f(n)=\mathrm{\Omega }(n^{\frac{1}{2}+ϵ})$, for $ϵ\le \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}\le cf(n)$ for $c=\frac{2}{3}$. So $T(n)=\mathrm{\Theta }(n)$.

d

Here, we have a = 2, b = 4, and $f(n)=\mathrm{\Theta }(n^2)$, and thus we have that $n^{{\log }_{b}a}=n^{{\log }_{4}2}=n^{\frac{1}{2}}$. Since $f(n)=\mathrm{\Omega }(n^{\frac{1}{2}+ϵ})$, for $ϵ\le \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}\le cf(n)$ for $c=\frac{1}{2}$. So $T(n)=\mathrm{\Theta }(n^2)$.

4.5-2

In Strassen's algorithm, $T(n)=\mathrm{\Theta }(n^{\lg 7})$. In Professor Caesar's algorithm, $T(n)=aT(\frac{n}{4})+\mathrm{\Theta }(n^2)$. In order to beat Strassen's algorithm, then Professor Caesar's algorithm cannot apply case 3, since $f(n)=\mathrm{\Theta }(n^2)$ which is polynomially larger than $\mathrm{\Theta }(n^{\lg 7})$.

We have that $n^{{\log }_{b}a}=n^{{\log }_{4}a}=n^{\frac{\lg a}{2}}$. If case 2 applies, then $f(n)=\mathrm{\Theta }(n^{\frac{\lg a}{2}})$, so $n^{\frac{\lg a}{2}}=n^2$, a = 16. And $T(n)=\mathrm{\Theta }(n^{\frac{\lg a}{2}}\lg n)=\mathrm{\Theta }(n^2\lg n)$ which cannot beat Strassen's algorithm.

So case 1 applies. And $T(n)=\mathrm{\Theta }(n^{\frac{\lg a}{2}})$, and we have $\frac{\lg a}{2}<\lg 7$, 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)=\mathrm{\Theta }(1)$, and thus we have that $n^{{\log }_{b}a}=n^{{\log }_{2}1}=1$. Case 2 applies, so $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\lg n)=\mathrm{\Theta }(\lg n)$.

4.5-4

Here, we have a = 4, b = 2, and $f(n)=\mathrm{\Theta }(n^2\lg n)$, and thus we have that $n^{{\log }_{b}a}=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)=\mathrm{\Theta }(n^2\lg n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\lg }^{k}n)$, where k = 1. So $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\lg }^{k+1}n)=\mathrm{\Theta }(n^2{\lg }^{2}n)=\mathrm{\Theta }((n\lg n{)}^2)$.

4.5-5