Problem Set 6

Recurrences 2

1 Master Method Recurrences

For each of the recurrences $T_i$ below, find $f_i$ such that $T_i = \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 = \Omega(n^{1 + \epsilon})$, so we are in the root heavy case.

To check that the regularity condition holds, we need to check that $a f(n/b) \leq c f(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) = \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) - \epsilon})$, so we are in the leaf heavy case. Thus $T_2(n) = \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) = \Theta(n^{\log_4(2)})$ so we are in the balanced case of the master theorem. Thus, $T_3(n) = \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) = \Theta(f)$.

Solution

Claim. $T(n) = \Theta(n)$.

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

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

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