# Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following:

$$\sum_{i=1}^n O(i)$$

is not the same as (I'm not using DNE because the book explicitly says "is not the same as")

$$O(1) + O(2) + \dots + O(n)$$

Why is this? How are we to explicitly represent the first summation if not with the second? As an extension of the previous question, how do we do asymptotic analysis on such a summation?

• Because when you add Big-O notation smaller terms disappear. See this possible duplicate. – 1201ProgramAlarm Aug 29 '19 at 1:17

So this $$\sum_{i=1}^n O(i)$$
means a placeholder for $$\sum_{i=1}^n f(i),$$
where $$f(i)$$ is an anonymous function from the set $$O(i)$$ — but it is always the same function in all terms of the sum. However, in $$O(1) + O(2) + \dots + O(n)$$, each term represents a placeholder for a (potentially) different anonymous function $$f_i$$ from the set $$O(i)$$. Note the book also says, the latter has "no clear interpretation", so it is quite meaningless.
Doc Brown answered your first question perfectly. Let me answer your second question. The expression $$O(i)$$ is a placeholder for a function which is bounded by $$Ci$$ for some $$C > 0$$. Therefore $$\sum_{i=1}^n O(i) \leq C \sum_{i=1}^n i = C \frac{n(n+1)}{2} = O(n^2).$$ Furthermore, this bound is tight, in the sense that $$n^2$$ cannot be replaced with any asymptotically smaller function. This is because $$i = O(i)$$, and $$\sum_{i=1}^n i = \Theta(n^2)$$.