What do you get when you add $O(n)$ to itself $n$ times?

I was watching this video on Algorithms and counting number of inversions and he mentioned being cautions when $$O(n) + O (n) = O(n)$$, saying that is not true if you add $$O(n)$$ to itself $$n$$ times. Is the answer $$O(n^2)$$?

The notation $$O(n)$$ stands for a function which is bounded by $$Cn$$ for some constant $$C>0$$ and large enough $$n$$.

If you have a two functions $$f_1,f_2$$ which are both $$O(n)$$, then so is their sum $$f_1+f_2$$: indeed, suppose that $$f_1(n) \leq C_1n$$ and $$f_2(n) \leq C_2n$$ for large enough $$n$$. Then $$f_1(n) + f_2(n) \leq (C_1 + C_2)(n)$$ for large enough $$n$$.

Similarly, if you have a single function $$f(n)$$ which is $$O(n)$$ and you add it to itself $$n$$ times then you get a function $$nf(n)$$ which is $$O(n^2)$$.

However, this fails when you add $$n$$ different functions which are $$O(n)$$. For example, consider the functions $$f_k(n) = kn$$ and the function $$g(n) = f_1(n) + \cdots + f_n(n)$$. Then $$f_k(n) = O(n)$$ for all $$k$$, but it is not true that $$g(n) = O(n^2)$$; rather, $$g(n) = \Theta(n^3)$$. (This means that $$cn^3 \leq g(n) \leq Cn^3$$ for some $$c,C>0$$ and large enough $$n$$.)

If we know that the functions $$f_k$$ are uniformly $$O(n)$$, that is, there is a single $$C>0$$ and a single $$N>0$$ such that $$f_k(n) \leq Cn$$ whenever $$n>N$$, then it does hold that $$f_k(1) + \cdots + f_k(n) = O(n^2)$$.

(It doesn't suffice to require just $$C$$ to be uniform. For example, if $$f_k(n) = n+k^2$$ then $$f_k(n) \leq 2n$$ for large enough $$n$$, but $$f_1(n) + \cdots + f_n(n) = \Theta(n^3)$$.)

• Could you show how you arrived at the cubic n? Jan 1 '21 at 18:22
• We have $\sum_{k=1}^n (n + k^2) = n^2 + \frac{n(n+1)(2n+1)}{6} = \frac{2n^3+4n^2+n}{6}$. Jan 1 '21 at 18:32
• Isn't it required that $C$ never be related to $n$? Jan 26 '21 at 12:33