Use a recursion tree to determine a good asymptotic upper bound
on the recurrence T(n) = 2T(n/3) + 2n.
Use the substitution method to verify your answer
Solve the recurrence equations by Substitution
a) T(n) = 4T (n/2) + n, T (1) = 1
b) T(n) = 4T (n/2) + n2 , T (1) = 1
c) T(n) = 4T (n/2) + n3 , T (1) = 1
Use a recursion tree to determine a good asymptotic upper bound
on the recurrence ?(?) = 3?(?/3) + ?. Use the substitution method
to verify your answer.
1. Using domain and range transformations, solve the following
recurrence relations:
a) T(1) = 1, T(n) = 2T(n/2) + 6n - 1
b) T(1) = 1, T(n) = 3T(n/2) + n^2 - n
Solve the given non-homogeneous recurrence relations:
an = an-1 + 6an-2 + f(n)
a)
an = an-1 + 6an-2 -
2n+1 with a0 = -4, a1= 5
b)
an = an-1 + 6an-2 + 5 x
3n with a0 = 2, a1 = 5
c)
an = an-1 + 6an-2 - 36n with
a0 = 10, a1= 40
Using the backward substitution method, solve the following
recurrence relations: a.T(n)= T(n−1)+3forn>1 ,T(1)=0
b.T(n)=3T(n−1) forn>1 ,T(1)=7 c.T(n)= T(n−1)+n for n>0
,T(0)=0 d.T(n)= T(n/2)+n for n>1 ,T(1)=1(solve for n=2k) e.T(n)=
T(n/3)+1forn>1 ,T(1)=1(solve for n=3k)