Prove or disprove: $\sum\limits_{i=1}^n i^2 = O(n^2) $

Question

Prove or disprove:

$$\sum_{i=1}^n i^2 = O(n^2) $$

If we want to prove this, find some summation that we know the $ O(n)$ runtime for, and is $ O(n^2) $ or smaller.

Otherwise, we could disprove this by finding some summation that is less than this one, but has a $O(n)$ runtime that is greater than $ O(n^2)$.

No idea where to go from here though. Any assistance is appreciated.

Answer 1

Did you know that $$\sum_{k=1}^n k^2=\frac{n(n+1)(2n+1)}6\text{ ? }$$

More generally, $$f_p(n)=\sum_{k=1}^n k^p$$ is a polynomial of degree $p+1$, with leading term $$\frac{n^{p+1}}{p+1}$$ You can prove this by induction.

Answer 2

Hint:

$$ \sum_{i=1}^n i^2 \geq \int_0^n x^2\,dx. $$