1. Solve the following:

Use iteration method to solve the following recurrences:

a) T(n) = 3T(n/3) + c, where c is a constant. Assume n is a power of 3 and T(1) = c. While solving it using iteration method, give explicit answers to the following questions. What is the general k^th term in this case? What value of k should be plugged in to get the answer? What is the answer?

b) T(n) = 2T(n-2) + c, where c is a constant. Assume n = 2m for some integer m and T(0) = c. While solving it using iteration method, give explicit answers to the following questions. What is the general k^th term in this case? What value of k should be plugged in to get the answer? What is the answer?

Use recursion tree method to solve the following recurrences. For each of the recurrences you need to draw a tree, and compute T(n) as the sum of all the nodes in the tree.

Assume that T(1) = c

c) T(n) = 4T(n/2) + c, where c is a constant.

d) T(n) = T(n-1) + cn, where c is a constant.