I am not able to solve the following recurrence relation:

$$ T(n) = \begin{cases} T(n-1) + n^2 & \text{if } n \ge 2, \\ 1 & \text{otherwise.}\\ \end{cases} $$

How do I start?

  • $\begingroup$ Search up the master's theorem in google. $\endgroup$
    – nir shahar
    Mar 10 at 20:28
  • $\begingroup$ Sum all the instances of the recurrence for $n=2,3,...,m$ and cancel the terms that appear on both sides. You get $T(m)=T(1)+2^2+3^2+...+m^2=1+2^2+3^2+...+m^2=\frac{m(m+1)(2m+1)}{6}$. $\endgroup$
    – plop
    Mar 10 at 21:47
  • $\begingroup$ @nir shahar, that’s quite useless advice. Master’s theorem can’t be used here. $\endgroup$
    – gnasher729
    Mar 11 at 19:26
  • 3
    $\begingroup$ Does this answer your question? Solving or approximating recurrence relations for sequences of numbers $\endgroup$
    – xskxzr
    Mar 18 at 11:41

In general, the recursion formula T(n) = T(n-1) + g(n), T(1) = c has the solution T(n) = c + sum of g(k) over 2 <= k <= n. No recursion, just a simple summation.


$$T(n)=T(1)+\sum_{i=2}^{n}i^2$$ $$T(n)=T(1)+\sum_{i=1}^{n}i^2-\sum_{i=1}^{1}i^2$$

So as @plop mentioned in comments, we have: $$\lim_{n\to \infty} T(n)=\frac{n(n+1)(2n+1)}{6}=O(n^3)$$


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.