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.

  • 1
    $\begingroup$ Both of your thoughts are correct, assuming $g_1(x),g_2(x)$ are positive (as they should be). $\endgroup$
    – hardmath
    Dec 24, 2016 at 5:42
  • 1
    $\begingroup$ asymptomatic notations are closed under summation Not as written, but rather $f_1+f_2=\mathcal{O}(|g_1|+|g_2|)$. $\endgroup$
    – dxiv
    Dec 24, 2016 at 5:43
  • $\begingroup$ @dxiv, ok, if $g_1(x)$ or $g_2(x)$ are negative, then $max(g_1(x), g_2(x))$ will hold, right? $\endgroup$
    – lu5er
    Dec 24, 2016 at 5:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – dxiv
    Dec 24, 2016 at 6:11
  • 1
    $\begingroup$ @Apy There was most likely some assumption of $f, g \ge 0$ hidden somewhere. $\endgroup$
    – dxiv
    Dec 24, 2016 at 6:14


You must log in to answer this question.

Browse other questions tagged .