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 '16 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 '16 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 '16 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 '16 at 6:11
  • 1
    $\begingroup$ @Apy There was most likely some assumption of $f, g \ge 0$ hidden somewhere. $\endgroup$ – dxiv Dec 24 '16 at 6:14

Your Answer

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

Browse other questions tagged or ask your own question.