Big O - Prove that the sum $\sum_{i=1}^n i^2 = O(n^3)$

Question

Question:

Show that $f(n) = \sum_{i=1}^n i^2 = O(n^3)$

Logically speaking, since the upper limit of $i$ is $n$ and the equation is $i^2$, it can never surpass $n^3$ if $c = 1$ and $n > 1$, therefore $i^2 \le cn^3$.

I just don't know how to prove it mathematically.

Answer 1

Your intuition is pretty good but your conclusion is off. If you are summing $i$ from $1$ to $n$, you know that $i \le n$, meaning that

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

Can you take it from here?

Answer 2

$$ \sum_{i=1}^{n}i^2=f\left(n\right)=\frac{n\left(n+1\right)\left(2n+1\right)}{6} $$ Hence $$ \frac{f\left(n\right)}{n^3}\underset{(+\infty)}{\sim}\frac{1}{3} $$ So it is not a $o\left(n^3\right)$ if I'm right ... Or you meant big $O$ ?

EDIT : Now you've corrected it you can use that $$ n+1 \leq 2n \ \text{ and } \ 2n+1 \leq 3n $$ Hence $$ \sum_{i=1}^{n}i^2=f\left(n\right) \leq \frac{n\left(2n\right)\left(3n\right) }{6}\leq n^3$$