Why is this algorithm $O(n^3)?$

Question

In a programming book that I'm currently reading it's stated that

$$\sum\limits_{i=1}^{n}i^2$$ is $O(n^3)$. My understanding was that $i\times i$ is a primitive operation and the complexity would be $O(n)$. What am I missing?

Answer 1

The expression $$ \sum_{i=1}^n i^2 $$ is not an algorithm. It is just a number. In fact, what the book really means is the function $$ n \mapsto \sum_{i=1}^n i^2. $$ Since $$ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{2n^3+3n^2+n}{6}, $$ we see that this sum is indeed $O(n^3)$, in fact, even $\Theta(n^3)$.

We often use big O notation in analyzing the running time of an algorithm. Quicksort runs in time $O(n\log n)$ (on average) since the function $T(n)$ measuring its average running time on inputs of length $n$ is $O(n\log n)$ — the function $T(n)$, not the algorithm itself.

Answer 2

As an addendum to the other fine answer, you don't actually need to calculate what the exact value of the summation is:

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

It's a very coarse upper bound, but that's good enough.

As an exercise, show that the sum is $\Omega(n^3)$ using a similar argument. It's a little trickier, because you need to find a lower bound that is cubic.

Answer 3

For some geometric intuition about the sum, consider building a pyramid out of stone blocks. The number of stones you need to build the first layer is $n^2$, the number of stones for the second layer is $(n-1)^2$, then for the next layer $(n-2)^2$ stones, and so forth until the very top layer which requires $1$ stone. In other words, the number of stones needed to build the pyramid is, $$\text{stones needed} = \sum_{i=1}^n i^2.$$

Now since your pyramid is made out of blocks and not smooth, it is not a "true pyramid". However, it is a pretty good approximation. In particular, your blocky pyramid contains a small true pyramid with $n\text{-by-}n$ base, and is contained in a large true pyramid with $(n+1)\text{-by-}(n+1)$ base. Since the volume of a true pyramid is $\frac{1}{3} \cdot \text{base} \cdot \text{height}$, and the pyramid has base area $n^2$ and height $n$, altogether this gives us the inequality of volumes, $$V(\text{small pyramid}) < V(\text{blocky pyramid}) < V(\text{large pyramid})$$ $$\frac{1}{3} n^3 < \sum_{i=1}^n i^2 < \frac{1}{3} (n+1)^3.$$

Here is a diagram showing what's going on for $n=4$: