1. Solve the recurrence relation T(n) = T(n 1) + 4, T(1) = 2 and prove your result is correct by induction. What is the order of growth?

2. Solve the recurrence relation T(n) = T(n 1) + n, T(1) = 1 and prove your result is correct by induction. What is the order of growth?

3. Solve the recurrence relation T(n) = 2T(n/2) + n, T(1) = 1 and prove your result is correct by induction. What is the order of growth?

4. I will give you a shortcut for solving recurrence relations like the previous problem called the Master Theorem.

Suppose T(n) = aT(n/b) + f(n) where f(n) = (n d ) with d 0. Then T(n) is:

(n d ) if a < bd (n d lg n) if a = b d

(n logb (a) ) if a > bd

Use the Master Theorem to solve the previous problem, explaining what the values are for a, b and d, as well as the order of growth.