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)

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.SolutionT(

Get Help Now

Submit a Take Down Notice

Tutor
Tutor: Dr Jack
Most rated tutor on our site