Week 4 - Recurrences
Notes
Master Theorem
T(n) = aT(\dfrac{n}{b}) + f(n), where a \geq 1, b > 1, then
Assignment - Due 10/20/2018
Credit: source code of questions are from walkccc.
4.3-6
Show that the solution to T(n) = 2T(\lfloor n / 2 \rfloor + 17) + n is O(n\lg n).
Suppose that T(n) = O(\lg n), then \exists c>0, letting
So when c \geq 35, n_0 = 35, the inequality holds, which is
4.3-7
Using the master method in Section 4.5, you can show that the solution to the recurrence T(n) = 4T(n / 3) + n is T(n) = \Theta(n^{\log_3 4}). Show that a substitution proof with the assumption T(n) \le cn^{\log_3 4} fails. Then show how to subtract off a lower-order term to make the substitution proof work.
If we suppose that \exists{c>0} letting T(n) = 4T(\dfrac{n}{3}) + n \leq cn^{\log_3{4}}:
But this lead to n \leq 0, which is impossible, the substitution proof above fails. Instead, if we suppose \exists{c>0}, letting T(n) = 4T(\dfrac{n}{3}) + n \leq cn^{\log_3{4}} - dn:
So when c>0, d \geq 3, the inequality holds, which is
4.3-8
Using the master method in Section 4.5, you can show that the solution to the recurrence T(n) = 4T(n / 2) + n^2 is T(n) = \Theta(n^2). Show that a substitution proof with the assumption T(n) \le cn^2 fails. Then show how to subtract off a lower-order term to make the substitution proof work.
If we suppose that \exists{c>0}, letting 4T(\dfrac{n}{2}) + n^2 \leq cn^2:
Dead end!
In fact, according to Master Theorem, the asymptotic bound of T(n) is \Theta(n^2\lg n). Suppose \exists c>0, \exists d>0, letting 4T(\dfrac{n}{2}) + n^2 \leq cn^2\lg n - dn:
So when c \geq 1, d > 0, T(n) = O(n^2\lg n).
Similarly, we can prove T(n) = \Omega(n^2\lg n). which is
4.3-9
Solve the recurrence T(n) = 3T(\sqrt n) + \log n by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.
Since T(n) = 3T(\sqrt{n}) + \lg{n}, let n = 2^k, then
Let S(k) = T(2^k), then
According to Master Theorem, we can suppose
then \exists c > 0, \exists d > 0, \exists e > 0, \exists f > 0 letting
So, when c>0, d > 0, e>0, f\geq 2, S(k) = \Theta(k^{\lg3}), which is
4.4-1
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 3T(\lfloor n / 2 \rfloor) + n. Use the substitution method to verify your answer.
Suppose n is exact power of 2, we can draw the tree:
- At level i, the size is \dfrac{n}{2^i}, and the number of nodes is i is 3^i, so the cost is
- Specifically, the size at the last level is 1, so the number of levels is \lg n, and the cost is:
The total cost of the tree is:
We use substitution to prove the conclusion above is right. Suppose T(n) = O(n^{\lg3}), \exists c>0, \exists d>0 letting
So, when c>0, d \geq 2, T(n) = O(n^{\lg3}).
4.4-2
Use a reccursion tree to determine a good asymptotic upper bound on the recurrence T(n) = T(n / 2) + n^2. Use the substitution method to verify your answer.
Suppose n is exact power of 2, we can draw the tree:
- At level i, the size is \dfrac{n}{2^i}, and the number of nodes is i, so the cost is \dfrac{n^2}{4^i}.
- Specifically, the size at the last level is 1, so the number of levels is \lg n, and the cost is 1. So the total cost of the tree is:
We use substitution to prove the conclusion above is right. Suppose T(n) = O(n^2), \exists c>0 letting T(n) \leq cn^2:
Thus the inequality holds, T(n) = O(n^2).
4.4-3
Use a reccursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 4T(n / 2 + 2) + n. Use the substitution method to verify your answer.
We can make a good guess by looking into T(n) = 4T(n / 2 + 2) + n instead. Suppose n is exact power of 2, we can draw the tree:
-
At level i, the size is \dfrac{n}{2^i}, and the number of nodes is 4^i, so the cost is 4^i \cdot \dfrac{n}{2^i} = 2^i{n}.
-
Specifically, the size at the last level is 1, so the number of levels is \lg n, and it has n^2 leaves. The total cost of the tree is:
We use substitution to prove the conclusion above is right. Suppose T(n) = O(n^2), \exists c>0, \exists d>0 letting T(n) \leq cn^2 - dn:
Thus the inequality holds, T(n) = O(n^2).
4.4-4
Use a reccursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 2T(n - 1) + 1. Use the substitution method to verify your answer.
We can draw the tree:
- At level i, the size is (n-i), and the number of nodes is 2^i, and the cost is 2^i.
- Specifically, the size at the last level is 1, so the number of levels is 2^n. The total cost of the tree is:
We use substitution to prove the conclusion above is right. Suppose T(n) = O(2^n), \exists c>0, \exists d>0 letting T(n) \leq c2^n - d:
Thus the inequality holds, T(n) = O(2^n).
4.4-5
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = T(n - 1) + T(n / 2) + n. Use the substitution method to verify your answer.
This is an unbalance tree, and its scale is between T(n) = 2T(\dfrac{n}{2}) + n and T(n) = 2T(n-1) + n. So guess T(n) = O(2^n), \exists a>0, \exists b>0 letting T(n) \leq a2^n-bn:
Thus the inequality holds, T(n) = O(2^n).
4.5-1
Use the master method to give tight asymptotic bounds for the following recurrences:
a. T(n) = 2T(n / 4) + 1.
b. T(n) = 2T(n / 4) + \sqrt n.
c. T(n) = 2T(n / 4) + n.
d. T(n) = 2T(n / 4) + n^2.
a. \Theta(n^{\lg_4 2}) = \omega(1) \Rightarrow \Theta(\sqrt{n})
b. \Theta(n^{\lg_4 2}) = \Theta(\sqrt{n}) \Rightarrow \Theta(\sqrt{n}\lg n)
c. \Theta(n^{\lg_4 2}) = o(n) \Rightarrow \Theta(n)
d. \Theta(n^{\lg_4 2}) = o(n^2) \Rightarrow \Theta(n^2)