Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 7 down vote accepted

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.

share|cite|improve this answer


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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.