1
$\begingroup$

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

$\endgroup$
6
$\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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ My answer does not suggest what you wrote. $\endgroup$ – Ashwin Ganesan Nov 20 '19 at 16:09
  • $\begingroup$ I thought the question just asked to express the sum in big o notation. It's now more clear what the op might have meant. $\endgroup$ – Ashwin Ganesan Nov 20 '19 at 16:11
  • $\begingroup$ Maybe I have misunderstood the question (as well as your answer). Don't think it deserves a downvote though :/ $\endgroup$ – Tassle Nov 20 '19 at 16:22
  • $\begingroup$ Your answer is good and probably is the right interpretation of the op’s question. Gave an upvote now. $\endgroup$ – Ashwin Ganesan Nov 20 '19 at 16:29
1
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\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.