Data Structures and Algorithms

Question 4 (30 points) Use the iteration technique to solve the following recurrence relations in terms of n. (10 points each) Hint: For part c you may find this summation formula useful: xn+1-1 =ox? 2-1 a) T(n) = 2T) +1,T(1) = 1 = b) T(n) = 2+T(n 1), T(0) = 2 c) T(n) = 3T(n 1) +1, T(1) = 1 2