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?
1
-
$\begingroup$ A very interesting document here that helps apprehending Summations. $\endgroup$– Mohamed Ennahdi El IdrissiMar 31, 2014 at 0:32
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
answered Mar 29, 2014 at 22:24
-
3$\begingroup$ but calculating the number can be done in O(1) using that formula $\endgroup$ Mar 30, 2014 at 1:25
-
1$\begingroup$ @ratchetfreak: In some models, yes, but that does not seem to be the question. $\endgroup$– Raphael ♦Mar 31, 2014 at 8:11
$\begingroup$
$\endgroup$
1
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.
answered Mar 31, 2014 at 1:05
-
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$ Jun 13, 2014 at 19:36
$\begingroup$
$\endgroup$
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$:
