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?

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

1 Answer 1


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.


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.