0
$\begingroup$

A question I was given

$T(0) = 1,$ $T(1)=0,$ $T(n)= 2T(n-2)$

I think the possible solution is $T(n)=2^n$

Proof: by induction. Base Case:

$n=0$ $T(0)=2^0=1$

Inductive Hypothesis: Assume for some $n$. $T(n)=2^n$ Show for $n+1$

$T(n+1)= 2(T(n-1))$ $=2(2^{n-1})$ $=2^n$

which is what I proposed. Is this correct? I'm a little confused because it says that $T(1)=0$, so it wouldn't make sense for $t(n)=2^n$. But I don't know how else I could prove the recurrence relation given as stated above.

$\endgroup$

1 Answer 1

1
$\begingroup$

This can be verified using the Master Theorem for decreasing functions

The recurrence relation can be written as $T(n)=2T(n-2)+O(1)$.

Comparing with the general recurrence here $a=2$, $b=2, k=0$

Using Case 2 of the theorem we get $T(n)= O(2^{\frac{n}{2}}*n^0) = O(2^{\frac{n}{2}})$

Even if you don't know the theorem, for such standard recurrences, one way is to draw the recurrence tree for it, and you can quickly figure out the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.