How can I show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$

Question

I am preparing for an exam, and one of the problems on the study guide is:

Show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$

If we declare n as some arbitrary number 5, then our summation would read $1^2$ + $2^2$ + $3^2$ + $4^2$ + $5^2$

Everything I have researched would suggest to me that this should be $O (n^2)$. How do we come up with $O (n^3)$?

Answer 1

Hint: Note that

$$\sum_{i=1}^n i^2 = 1^2 + 2^2 + \cdots + n^2 \le n^2 + n^2 + \cdots + n^2.$$

Answer 2

It is not difficult to show that \begin{align} \sum_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6} = \frac{n^{3}}{3} + \frac{n^{2}}{2} + \frac{n}{6} \end{align} Since the highest power on $n$ is 3 then it can be stated that \begin{align} \sum_{i=1}^{n} i^{2} \sim \mathcal{O}(n^{3}) \end{align}