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?
Why is this algorithm $O(n^3)?$
time complexity
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.