I was hoping to solve the following recurrence by performing a simple substitution followed by the master's method: $$T\left(n\right)=T\left(n-1\right)+n^2$$ I did $$S\left(2^n\right)=S\left(2^{n-1}\right)+\left(2^n\right)^2$$ Thus $$S\left(m\right)=S\left(\frac{m}{2}\right)+m^2$$ Which using the master's method yields $$T\left(n\right)=\Theta \left(\left(2^n\right)^2\right)$$ However, the correct answer to this is: $$T\left(n\right)=\Theta \left(n^3\right)$$ So what was wrong with my substitution?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ The first step: instead of $(2^n)^2$ it's still simply $n^2$. $\endgroup$ – Dmitry Dec 4 '20 at 20:13
-
$\begingroup$ Oh, that makes sense. Thank you. $\endgroup$ – Essam Dec 4 '20 at 20:25
Add a comment
|
$\begingroup$
$\endgroup$
The key thing to note is that you are replacing $T(n)$ function with an exponential $S(n)=2^n$. The variables do not change just the functions. So, $n^2$ stays.
