I'm trying to solve this the recurrence : $$ T(n)=\begin{cases} 1, & \text{ if } n = 1 \\ T(n-1) +n(n-1), & \text{ if } n \geq 2 \end{cases} $$

  • 1
    $\begingroup$ $1 + \dfrac{(n-1)n(n+1)}3$, if you want a closed formula. $\endgroup$ – John L. Apr 24 at 16:21
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Apr 24 at 21:58

Since $T(n)=T(n-1)$, using induction we can prove that $T(n)= 1 + \sum_{k=1}^n k(k-1) \le 2\sum_{k=1}^n k(k-1)$

Now, calculating $\sum_{k=1}^n k(k-1)$ gives us:

$\sum_{k=1}^n k(k-1)=\sum_{k=1}^n (k^2 - k) = \sum_{k=1}^n k^2 - \sum_{k=1}^n k$

Using this formula, we know that $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$, and its not hard to show that $\sum_{k=1}^n k = \frac{n (n+1)}{2}$

Therefore, $T(n) \le 2\left(\frac{n(n+1)(2n+1)}{6} - \frac{n (n+1)}{2}\right) = O(n^3)$

  • $\begingroup$ A lower bound can be given using the same proof, replace the $\le$ with $\ge$ and replace the multiplication by $2$ with multiplication by $\frac{1}{2}$ $\endgroup$ – nir shahar Apr 24 at 14:07
  • $\begingroup$ I don't understand the second step. Can you explain that line? $\endgroup$ – Phȕc Luog Apr 24 at 14:25
  • $\begingroup$ Can you be more specific about what you didn't understand? What equation in the line don't you understand? $\endgroup$ – nir shahar Apr 24 at 14:26
  • $\begingroup$ The line that you using induction to prove $$ T(n)=1+∑nk=1k(k−1)≤2∑nk=1k(k−1) $$ $\endgroup$ – Phȕc Luog Apr 24 at 14:38
  • $\begingroup$ $T(n)=T(n-1)+n(n-1)=T(n-2)+(n-1)(n-2)+n(n-1)=T(n-3)+(n-2)(n-3)+(n-1)(n-2)+n(n-1)=...=T(1) + \sum_{k=1}^n k(k-1) = 1 + \sum_{k=1}^n k(k-1)$ $\endgroup$ – nir shahar Apr 24 at 14:39

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.