# Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: $$\sum_{k=1}^{n-1} O(n).$$

You should be very careful when summing up a variable number of terms in asymptotic notation, as the result actually depends on the hidden constants.

Consider the following example: $$f_i(n) = i\cdot n$$ for all integers $$i$$ and $$n$$. Then, for any integer $$i$$, $$f_i(n) \in O(n)$$.

If you are not careful, you could end up writing something like: $$\sum_{i=1}^n f_i(n) = \sum_{i=1}^n O(n) = O(\sum_{i=1}^n n) = O(n^2).$$ And get $$O(n^2)$$. But this is totally wrong!

If you do the computation without the asymptotic notation, you get: $$\sum_{i=1}^n f_i(n) = \sum_{i=1}^n i\cdot n = n\sum_{i=1}^n i = n\frac{n(n+1)}{2} = \frac{n^2(n+1)}{2}.$$ And this is not in $$O(n^2)$$, as it is in $$\Theta(n^3)$$.

Now some authors define $$\sum_{i=1}^n O(n)$$ as meaning that the hidden constants are the same for every $$O$$ and in this case you can sum things together. But this is not always the case so I recommend not using $$O$$ notation with variable-length sums (as well as when doing induction, where similar problems appear).

To express the sum over k in big o notation, use the formulae that express the sum of the $$i$$th powers of the first $$n$$ positive integers as a polynomial of degree $$i+1$$.

For example, $$\sum_{k=1}^n k$$ is the quadratic function $$n(n+1)/2 = O(n^2)$$. The sum $$\sum_{k=1}^n k^2$$ is a cubic polynomial in $$n$$ and hence is $$O(n^3)$$, etc.

• Be careful, $O$ notation can be quite treacherous and doing stuff like this can lead to false results! (see my answer) Nov 20 '19 at 15:32