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