Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
