1
$\begingroup$

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?

$\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
1
$\begingroup$

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.

$\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.