1
$\begingroup$

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

$\endgroup$
1
8
$\begingroup$

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).

$\endgroup$
0
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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