Halp please Solve the recurrences relations to within big Th
Halp please.
Solve the recurrences relations to within big Theta accuracy. Assume that
T(n) = 1 for n <=1 and the recurrence given is for n > 1.
Solution
T(n) = T(n-2) + 2^n.
= T(n-4) +2^(n-2) +2^n.
and continuing till base case, where T(n) =1.
we have 1 + 2^2 + 2^4 + . . . + 2^n = theta( (4^(n+1) -1)/3) =Theta(4^(n/2+1))=Theta(2^n)
