1
$\begingroup$

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?

$\endgroup$
1

3 Answers 3

12
$\begingroup$

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.

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

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.

$\endgroup$
1
  • 1
    $\begingroup$ $ \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) $ $\endgroup$
    – gardenhead
    Commented Jun 13, 2014 at 19:36
2
$\begingroup$

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

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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