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)$?
2 Answers
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)$.)
-
$\begingroup$ Could you show how you arrived at the cubic n? $\endgroup$ Jan 1, 2021 at 18:22
-
$\begingroup$ 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}$. $\endgroup$ Jan 1, 2021 at 18:32
-
-
$\begingroup$ I think it works better as an exercise. $\endgroup$ Jan 1, 2021 at 19:33
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.
-
$\begingroup$ Isn't it required that $C$ never be related to $n$? $\endgroup$ Jan 26, 2021 at 12:33