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

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?

• A very interesting document here that helps apprehending Summations. Mar 31, 2014 at 0:32

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.

• but calculating the number can be done in O(1) using that formula Mar 30, 2014 at 1:25
• @ratchetfreak: In some models, yes, but that does not seem to be the question.
– Raphael
Mar 31, 2014 at 8:11

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.

• $\sum_{i=0}^n i^2 \geq \sum_{i=n/2}^n i^2 \geq \sum_{i=n/2}^n (n/2)^2 = (n/2)^3 = \Omega(n^3)$ Jun 13, 2014 at 19:36

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