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\).