Algorithms (CC4010) - 2018/2019 DCC/FCUP
Exercises #3
Solving Recurrences
Theoretical Background
4 methods for solving recurrences:
• Unrolling: unroll the recurrence to obtain an expression (ex: summation) you can work with
• Substitution: guess the answer and prove by induction
• Recursion Tree: draw a tree representing the recursion and sum all the work done in the nodes
• Master Theorem: If the recurrence is of the form aT(n/b) + cnk (this is one version of the theorem):
(1) T (n) = Θ(nk ) if a < bk
(2) T (n) = Θ(n log n) if a = bk
k
(3) T (n) = Θ(nlogb a ) if a > bk
For the following exercises, assume that T (n) takes constant time for sufficiently small n.
1. Solve the following recurrences by unrolling. State the answer using Θ notation.
(a) T (n) = T (n − 2) + 1
(b) T (n) = T (n − 1) + n2
2. Show that the following conjectures are true by using the substitution method.
(a) T (n) = T (n − 1) + 2 is Θ(n)
(b) T (n) = 2T (n/2) + n is Θ(n log n)
3. Draw a recursion tree for the following recurrences and use it to obtain asymptotic bounds as tight as
possible.
(a) T (n) = 3T (n/2) + n
(b) T (n) = T (n/2) + n2
4. Solve the following recurrences using the master method:
(a) T (n) = 2T (n/4) + 1
√
(b) T (n) = 2T (n/4) + n
(c) T (n) = 2T (n/4) + n
(d) T (n) = 2T (n/4) + n2
1
5. Consider the recurrence T (n) = 8T (n/2) + n2
(a) Use the substitution method to try to prove that T (n) = O(n2 ). The proof should fail. Can you
understand why?
(b) Use the master method to find the a tight asymptotic bound. Try to prove that bound directly.
Does the math work?
(c) Use a stronger induction hypothesis (by subtracting a lower order term) and make a correct proof
of that tighter bound.
6. Give asymptotic upper and lower bounds (as tight as possible) for the following recurrences. You can
use any method you want.
(a) T (n) = 7T (n/3) + n2
(b) T (n) = 7T (n/2) + n2
(c) T (n) = 2T (n/4) + n2
(d) T (n) = T (n − 2) + n3
(e) T (n) = T (n/2) + T (n/4) + T (n/8) + n
1
(f) T (n) = T (n − 1) + n
(g) T (n) = 4T (n/3) + n log2 n
