Can someone help me build what the recursion tree would look like for this problem? Would the next level be $n-3$, and then $n-4$?
Asked
Active
Viewed 131 times
2 Answers
2
I like moving the extra term to the front when solving these kinds of problems. $$\begin{align} T(n)&=1+2T(n-2)\\ &=1+2(1+2T(n-4))=1+2+4T(n-4)\\ &=1+2+4(1+2T(n-6))=1+2+4+8T(n-6)=\dots\\ &=(2^{n/2}-1)+2^{n/2}T(0)\\ &=\Theta(2^{n/2}) \end{align}$$
Parcly Taxel
- 103,344
-
What if the equation was T(n) = 2T(n-4) + 1 would the next level in the tree be (n-8) and then (n-12) ? @ParclyTaxel – Lucy Jones Feb 03 '20 at 14:04
-
@LucyJones Yeah, something like that, and it'd be $\Theta(2^{n/4})$. – Parcly Taxel Feb 03 '20 at 14:05
-
But shouldn't the answer be Big Theta (2^n) how are you getting Big Theta (2^n/2) – Lucy Jones Feb 03 '20 at 14:11
-
@LucyJones Yeah, it should be $\Theta(2^n)$ for the modified one. – Parcly Taxel Feb 03 '20 at 14:12
-
Ok, and for this equation T(n) = 2T(n-4) +1 for the modified version it would still be Big Theta (2^n) right? – Lucy Jones Feb 03 '20 at 14:13
-
@LucyJones Yes. – Parcly Taxel Feb 03 '20 at 14:13
0
Let $T(n)=2^{\frac{n}{2}}. A(n)$ $$. $$ Hence $T(n-2)=2^{\frac{n-2}{2}}.A(n-2)$ put in given equation we get $$2^{\frac{n}{2}}A(n)=2^{\frac{n}{2}}A(n-2)+1$$ $$\therefore A(n)-A(n-2)=2^{-\frac{n}{2}}$$ $$\sum_{n=2}^{n} (A(n)-A(n-2))=\frac{2^{\frac{n-1}{2}}-1}{2^{\frac{n}{2}}}=y \,(say)$$ Hence $ A(n)+A(n-1)-A(0)-A(1)=y$ $$T(n).2^{-\frac{n}{2}}+T(n-1).2^{-\frac{n-1}{2}}=y+T(0)+\frac{T(1)}{\sqrt{2}}$$
Rajan
- 461