Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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

2 Answers 2

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|improve this answer

Hint:

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

share|improve this answer

Your Answer

 
discard

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.