How do I show that $\sum_{i=0}^n i^2 = O(n^3)$?

Question

Do I have to know the formula for the summation? Why?

Answer 1

If your goal is only to find an approximate bound, there are several tricks: Let $s > 0$.

1. Using the largest summand, we get $$ \sum_{k=1}^{n} k^{s} \leq n \cdot n^{s} = n^{s+1}.$$

2. To make the constant small, $$ \sum_{k=1}^{n} k^{s} \leq \sum_{k=1}^{n} \int_{k}^{k+1} x^{s} \, ds \leq \int_{0}^{n+1} x^{s} \, ds = \frac{(n+1)^{s+1}}{s+1}. $$ Indeed, this is not far from the truth as $$ \sum_{k=1}^{n} k^{s} = \frac{n^{s+1}}{s+1} + \mathcal{O}(n^{s}). $$

Answer 2

Suppose that you do not know the formula for the summation. But you do know the following:

$$p(n) = \sum_{i=0}^n i^2\\ p(n+1) - p(n) = (n+1)^2 = O(n^2)\\ (n+1)^2 - n^2 = 2n + 1 = O(n)\\ 2(n+1)-1 - (2n - 1) = 2 = O(1)$$

This is only an intuitive approach; a more rigorous approach could make use of binomial forms and note that $p(n)$ must have a term $\binom n 3$ in it, therefore $p(n) = O(n^3)$.