# Summation of two asymptotic functions

Suppose we have $f_1(x) = O(g_1(x))$ and $f_2(x) = O(g_2(x))$, then what is $(f_1(x) + f_2(x))$?

What I know is asymptomatic notations are closed under summation. So, $(f_1(x) + f_2(x)) = O((g_1(x) + g_2(x))$

But now my question is first am I right?

If so, then why the answer cannot be $O(\max(g_1(x),g_2(x)))$ ? For example, $O(n + \log(n)) = O(\max(n, \log(n))) = O(n)$

Thanks in advance.

• Both of your thoughts are correct, assuming $g_1(x),g_2(x)$ are positive (as they should be). – hardmath Dec 24 '16 at 5:42
• asymptomatic notations are closed under summation Not as written, but rather $f_1+f_2=\mathcal{O}(|g_1|+|g_2|)$. – dxiv Dec 24 '16 at 5:43
• @dxiv, ok, if $g_1(x)$ or $g_2(x)$ are negative, then $max(g_1(x), g_2(x))$ will hold, right? – lU5er Dec 24 '16 at 5:46
• @Apy The definition of $\mathcal{O}$ only ever refers to the absolute values of the functions involved. The $\max$ alternative you propose compares signed values, not absolute ones, so it can't possibly work. If your real question is why $\mathcal{O}(n+\ln(n))=\mathcal{O}(n)$ (which is indeed the case, since $\ln(n) / n \to 0$) then you should rather ask that directly. – dxiv Dec 24 '16 at 6:11
• @Apy There was most likely some assumption of $f, g \ge 0$ hidden somewhere. – dxiv Dec 24 '16 at 6:14