# What's wrong with this substitution for master's method

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?

• The first step: instead of $(2^n)^2$ it's still simply $n^2$.
– user114966
Dec 4 '20 at 20:13
• Oh, that makes sense. Thank you. Dec 4 '20 at 20:25

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.