2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Could you show how you arrived at the cubic n? $\endgroup$ Jan 1 '21 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 '21 at 18:32
  • $\begingroup$ Could I add that to your answer? $\endgroup$ Jan 1 '21 at 18:46
  • $\begingroup$ I think it works better as an exercise. $\endgroup$ Jan 1 '21 at 19:33
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Isn't it required that $C$ never be related to $n$? $\endgroup$ Jan 26 '21 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.