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?
4
-
$\begingroup$ Search up the master's theorem in google. $\endgroup$– nir shaharMar 10, 2021 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$– plopMar 10, 2021 at 21:47
-
$\begingroup$ @nir shahar, that’s quite useless advice. Master’s theorem can’t be used here. $\endgroup$– gnasher729Mar 11, 2021 at 19:26
-
3$\begingroup$ Does this answer your question? Solving or approximating recurrence relations for sequences of numbers $\endgroup$– xskxzrMar 18, 2021 at 11:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
$$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)$$