Recurrence examples
Give asymptotic upper and lower bounds for \(T(n)\) in each of the following recurrences. Assume that \(T(n)\) is constant for \(n \leq 2\). Make your bounds as tight as possible, and justify your answers.
\(T(n) = 2T(n/2) + n^4\).
\(T(n) = T(7n/10) + n\).
\(T(n) = 16T(n/4) + n^2\).
\(T(n) = 7T(n/3) + n^2\).
\(T(n) = 7T(n/2) + n^2\).
\(T(n) = 2T(n/4) + \sqrt n\).
\(T(n) = T(n - 2) + n^2\).
Let’s revisit Master Theorem, as we’ll use that to solve all of these recurrences:
\[T(n) = aT(n/b) +f(n)\]
If \(f(n) = O(n^{\log_b a - \epsilon})\) for some constant \(\epsilon > 0\), then \(T(n) = \Theta(n^{\log_b a})\).
If \(f(n) = \Theta(n^{\log_b a})\), then \(T(n) = \Theta(n^{\log_b a} \lg n)\).
If \(f(n) = \Omega(n^{\log_b a + \epsilon})\) for some constant \(\epsilon > 0\), and if \(af(n/b) \leq cf(n)\) for some constant \(c < 1\) and all sufficiently large \(n\), then \(T(n) = \Theta(f(n))\).
A
Here, \(a = 2\) and \(b = 2\). So, \(\log_b a = 1\).
And, \(f(n) = n^4 = n^{1 + 3} = \Omega(n^{\log_b a + \epsilon})\) for \(\epsilon = 3\).
\(af(n/b) = 2f(n/2) = n^4/8 \leq cn^4\) for some constant \(1/8 < c < 1\) and \(n \geq 1\).
We can apply case 3: \(T(n) = \Theta(n^4)\).
B
Here, \(a = 1\) and \(b = 10/7\). So, \(\log_b a = 0\).
And, \(f(n) = n = n^{0 + 1} = \Omega(n^{\log_b a + \epsilon})\) for \(\epsilon = 1\).
\(af(n/b) = f(7n/10) = 7n/10 \leq cn\) for some constant \(7/10 < c < 1\) and \(n \geq 1\).
We can apply case 3: \(T(n) = \Theta(n)\).
C
Here, \(a = 16\) and \(b = 4\). So, \(\log_b a = 2\).
And, \(f(n) = n^2 = \Theta(n^{\log_b a})\).
We can apply case 2: \(T(n) = \Theta(n^2 \lg n)\).
D
Here, \(a = 7\) and \(b = 3\). So, \(\log_b a = 1.77\).
And, \(f(n) = n^2 = n^{1.77 + 0.23} = \Omega(n^{\log_b a + \epsilon})\) for \(\epsilon = 0.23\).
\(af(n/b) = 7f(7n/3) = 7n^2/9 \leq cn^2\) for some constant \(7/9 < c < 1\) and \(n \geq 1\).
We can apply case 3: \(T(n) = \Theta(n^2)\).
E
Here, \(a = 7\) and \(b = 2\). So, \(\log_b a = 2.8\).
And, \(f(n) = n^2 = n^{2.8 - 0.8} = O(n^{\log_b a - \epsilon})\) for \(\epsilon = 0.8\).
We can apply case 1: \(T(n) = \Theta(n^{\lg 7})\).
F
Here, \(a = 2\) and \(b = 4\). So, \(\log_b a = 1/2\).
And, \(f(n) = \sqrt n = \Theta(n^{\log_b a})\).
We can apply case 2: \(T(n) = \Theta(\sqrt n \lg n)\).
G
This recurrence is not of the form where we can apply Master theorem. We’ll need to solve this in other methods that we know of.
Let’s solve it by expanding the recurrence:
\[\begin {aligned} T(n) &= T(n - 2) + n^2 \\ &= T(n - 4) + (n - 2)^2 + n^2 \\ &= T(n - 6) + (n - 4)^4 + (n - 2)^2 + n^2 \\ &= T(0) + 2^2 + 4^2 + \cdots + (n - 4)^2 + (n - 2)^2 + n^2 \\ &= T(0) + \sum_{i = 0}^{n/2} (n - 2i)^2 \\ &= T(0) + \sum_{i = 0}^{n/2} n^2 - \sum_{i = 0}^{n/2} 4ni + \sum_{i = 0}^{n/2} 4i^2 \\ &= T(0) + \Theta(n^3) - \Theta(n^3) + \Theta(n^3)\\ &= \Theta(n^3) \end {aligned}\]