[Solved]: Why is this algorithm $O(n^3)?$

Problem Detail: 

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?

Asked By : planetp

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23232

3.2K people like this

 Download Related Notes/Documents