Big-O notation, prove the following: $\sum\limits_{k=3}^n(k^2 - 2k)$ is $O(n^3)$.

Question

Use the definition of Big-O notation to prove the following:

$\sum\limits_{k=3}^n(k^2 - 2k)$ is $O(n^3)$.

Can someone please give me some hints on how to expand $\sum\limits_{k=3}^n(k^2 - 2k)$?

Answer 1

The easiest way to conclude that it is $\mathcal{O}(n^3)$ is to note that $$k^2 - 2k < k^2 \leq n^2, \,\,\,\,\, \forall k \in \{3,4,\ldots,n\}$$ You could in fact evaluate the sum exactly and then prove that it is $\mathcal{\Omega}(n^3)$. Make use of the fact that $$\sum_{k=1}^n k^2 = \dfrac{n(n+1)(2n+1)}6 \text{ and } \sum_{k=1}^n k = \dfrac{n(n+1)}2$$

Move your mouse over the gray area below for the complete solution.

Note that$$\sum_{k=3}^n (k^2-2k) = \sum_{k=3}^n k^2 - 2\sum_{k=3}^nk = \dfrac{n(n+1)(2n+1)}6-1^2-2^2 - 2 \left(\dfrac{n(n+1)}2-1-2\right)$$The above simplifies to$$\dfrac{(n-2)(n-1)(2n+3)}6$$

Answer 2

You don’t actually have to work very hard at all:

$$\sum_{k=3}^n\left(k^2-2k\right)\le\sum_{k=3}^nk^2\le\sum_{k=3}^nn^2=(n-2)n^2\le n^3\;.$$

In other words, don’t expand the sum: bound it instead. As you can see, even a pretty crude bound works fine here.