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

Question

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)$?

Answer 1

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

Answer 2

What’s both important and confusing is that the two n’s in “adding up n O(n) functions” are not the same. And each of the O(n) functions has its own C, and it’s own n0.

Obviously adding n constants (the “C”s) is not necessarily O(n), for example if the n-th function has C = 2^n. And for the k-th function, the Limitation for n (n >= n0) might only apply for n0 = 2^k. So when you add these n functions, the Big-O limitation doesn’t apply to most of them.