Summation of big oh terms

Question

I read about asymptotic notation .I understood the limit definition of big oh notation.But while going about calculating O(1)+O(2)+.......…..+O(n),the sum comes out to be O(n ^2).Can anyone explain the same?

Answer 1

Due to the fact that $O(c) = O(1)$ where $c$ is any constant, I think your concern is this: if $f(n) = O(n)$ and if $$g(n) = \sum_{i=1}^n f(i)$$ then why is it true that $g(n) = O(n^2)$?

It is misleading to write something like $$g(n) = \sum_{i=1}^n O(i).$$ We do not view each particular instance of $f(i)$ as being $O(i)$; the statement $f(n) = O(n)$ is a statement about $f$ as a function of $n$, not about $f$ at any particular value.

So how do we go about proving that $g(n) = O(n^2)$? Well, because $f$ is $O(n)$, there exist constants $C$ and $n_0$ such that $|f(n)| \ge Cn$ for all $n \ge n_0$. So for $n \ge n_0$, we split the sum and use the triangle inequality to approximate: $$|g(n)| \le \sum_{i=1}^{n_0-1} |f(i)| + \sum_{i=n_0}^n |f(i)| \le C' + \sum_{i=n_0}^n Ci.\tag{1}$$ Here $C'$ is just the constant value of the first $n_0$ terms. We're allowed to be very loose in our estimates, so in the second sum in (1) we'll throw back in the numbers from $1$ to $n_0-1$ to get an even bigger bound: $$|g(n)| \le C' + C \sum_{i=1}^n i = C' + \frac{Cn(n+1)}{2}.\tag{2}$$ It should be clear now that the right hand side of (2) is $O(n^2)$, by which I mean it is bounded by a constant multiple of $n^2$. Indeed, $$C' + \frac{C}{2}(n(n+1)) = C' + \frac{C}{2}(n^2 + n) \le C'n^2 + \frac{C}{2}(n^2 + n^2) = (C' + C)n^2.$$