Big O has a correct representation?

Question

Let's say I have two function that run, respectively, in O(n) and O(m). For representational purposes, is it wrong to represent it as O(n)+O(m) instead of O(n+m)?

I was doing a test in which the representation O(n) + O(m) was marked wrong

Answer 1

These two notations do not mean the same thing.

O(m) means the set of all functions which asymptotically do not grow faster than m. So strictly speaking, O(m) + O(n) is not proper notation because these are two sets, not two functions; you cannot add sets together like this. However, we might informally write this to mean "the sum of some function in O(m) and some function in O(n)", or the set of all such sums, if the reader will know from context that that is what it's supposed to mean.

Clearly, every sum of two functions from O(m) and O(n) respectively is a member of O(m + n). So the question is then whether the converse holds: is it true that every function in O(m + n) can be written as a sum of two functions in O(m) and O(n) respectively? I don't know off the top of my head, but if you consider the function max(m, n), it doesn't seem like it could ever equal the sum of any two functions from O(m) and O(n) respectively. (Note that it's not enough to find two functions whose sum is an upper bound for max(m, n); it has to equal max(m, n) since otherwise max(m, n) is not a member of the set of all such sums.) So if you claim that these two sets, which are defined differently, actually are equal, then the onus is on you to offer a proof.

Now, it may be the case that in your test, the question did concern a function which could be represented as some function in O(m) plus some function in O(n); I don't know, since we haven't seen the test question. But even so, as mentioned earlier, "O(m) + O(n)" is not proper notation and it would normally only be written informally, so for that reason alone your answer might have been marked incorrect.