Problem Set 6

Recurrences 2

1 Master Method Recurrences

For each of the recurrences $T_i$ below, find $f_i$ such that $T_i=\mathrm{\Theta }(f_i)$. Prove your work. Use the master method.

1.1

$T_1(n)=2T_1(n/2)+n^4$

Solution

Apply the master theorem with $a=2,b=2,f(n)=n^4$. Note that $n^{{\log }_2(2)}=n$ We have $n^4=\mathrm{\Omega }(n^{1+ϵ})$, so we are in the root heavy case.

To check that the regularity condition holds, we need to check that $af(n/b)\le cf(n)$ for some $c<1$ and all sufficiently large $n$. We have $2(n/2{)}^4=n^4/8$, so we can take $c=1/8$.

Thus, the master theory applies and we have $T_1(n)=\mathrm{\Theta }(n^4)$.

1.2

$T_2(n)=7T_2(n/2)+n^2$

Solution

Apply the master theorem with $a=7,b=2,f(n)=n^2$. Note that $n^{{\log }_2(7)}=n^{2.81}$ We have $n^2=O(n^{{\log }_2(7)-ϵ})$, so we are in the leaf heavy case. Thus $T_2(n)=\mathrm{\Theta }(n^{{\log }_2(7)})$.

1.3

$T_3(n)=2T_3(n/4)+\sqrt{n}$

Solution

Apply the master theorem with $a=2,b=4,f(n)=\sqrt{n}$. Note that $n^{{\log }_4(2)}=\sqrt{n}$. We have $f(n)=\mathrm{\Theta }(n^{{\log }_4(2)})$ so we are in the balanced case of the master theorem. Thus, $T_3(n)=\mathrm{\Theta }(\sqrt{n}\log (n))$.

2 Unbalanced Recurrences

2.1

Use any method you want to solve the following recurrence. $$T(n)=n+T(n/5)+T(7n/10)$$

By ‘solve the recurrence’, I mean find $f$ such that $T(n)=\mathrm{\Theta }(f)$.

Solution

Claim. $T(n)=\mathrm{\Theta }(n)$.

Note that $T(n)=\mathrm{\Omega }(n)$ since $T(n)=n+T(n/5)+T(7n/10)\ge n$, since $T$ is positive.

Thus, to show that $T(n)=\mathrm{\Theta }(n)$ it suffices to show that $T(n)=O(n)$. Use the substitution method. $$\begin{array}{rl}T(n)& =n+T(n/5)+T(7n/10)\\ & \le n+cn/5+7cn/10\\ & =(1+9c/10)n\end{array}$$

We need this expression to be at most $cn$. Solving for $c$ we need $c\ge 10$.