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

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.

-
for the long form of summation just count the operations, you'll have $n$ number of multiplications and $n-1$ number of additions so the order is $O(n)$. However, when you go beyond the "integer" size of the computer/language you should count for that as well. Perhaps that's the question asked here. –  karakfa May 20 '13 at 21:33

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.
$$\sum_{i=1}^n i^2 \geq \int_0^n x^2\,dx.$$