Comparing complexity of O(n+m) and O(max(n,m))

Question

I had a job interview today. And was asked about complexity of std:set_intersection. When I was answering I mentioned that

O(n+m)

is equal to:

O(max(n,m))

I was told that this is incorrect. I was unsuccessfully trying to show equivalence with:

O(0.5*(n+m)) ≤ O(max(n,m)) ≤ O(n+m)

My question is: am I really incorrect?

Answer 1

For all m, n ≥ 0 it is valid that max(m, n) ≤ m + n → max(m, n) in O(m + n), and m + n ≤ 2max(m, n) → m + n in O(max(m, n)).

Thus O(max(m, n)) = O(m + n).

ADDENDUM: If f belongs O(m + n) then a constant D > 0 exists, that f(n, m) < D * (m + n) for m and n large enough. Thus f(n, m) < 2 D * max(m, n), and O(m + n) must be a subset of O(max(m, n)). The proof of O(max(m, n)) is a subset of O(m + n) is made analogously.

Answer 2

Well you have totally right about O(n+m) is equal to O(max(n,m)),even more precise we can prove Θ(n+m)=Θ(max(n,m) which is more tight and proves your sentence. The mathematical proof is (for both big-O and Θ) very simple and easy to understand with common sense. So since we have a mathematical proof which is a way to say something but in a more well defined and strict way which doesn't leaves any ambiguity.

Though you was (wrongly) told that this is incorrect because if we want to be very precise this is not the appropriate - mathematical way to express that order of max(m,n) is same as m+n. You used the words "is equal" referring to big-O notation but what is the definition of big-O notation?

It is referred to Sets. Saying max(n+m) belongs to O(m+n) is the most correct way and vice versa m+n belongs to O(max(m,n)). In big O notation is commonly used and accepted to say m+n = O(max(n,m)).

The problem caused is that you didn't try to refer to the order of a function like f is O(g) but you tried to compare Sets O(f) and O(g).But proving two infinite sets are equal is not easy (and that may confused the interviewer).

We can say Sets A and B are identical(or equal) when contain same elements (we do not try to compare but instead refer to elements they contain so they must be finite). And even identification can't be easily applied when talking about Big O Sets.

Big O of F is used to notate that we are talking about the Set that contains all functions with order greater or equal than F. How many functions are there??

Infinite since F+c is contained and c can take infinite values.

How could you say two different Sets are identical(or equal) when they are infinite ,well it is not that simple.

So I understand what you are thinking that n+m and max(n,m) have same 
order but **the right way to express that** is by saying n+m is    
O(max(n,m)) and max(n,m)is O(m+n) ( O(m+n) is equal to O(max(m,n)) 
may better requires a proof).

One more thing, we said that these functions have same order and this is absolutely mathematically correct but when trying to do optimization of an algorithm and you may need to take into account some lower order factors then maybe they give you slightly different results but the asymptotic behavior is proved to be the same.

CONCLUSION

As you can read in wikipedia (and in all cs courses in every university or in every algorithm book) Big O/θ/Ω/ω/ο notations helps us compare functions and find their order of growth and not for Sets of Functions and this is why you were told you were wrong. Though is easy to say O(n^2) is subset of O(n) it is very difficult to compare infinite to say if two sets are identical. Cantor have worked on categorizing infinite sets, for example we know that natural numbers are countable infinite and real numbers are uncountable infinite so real numbers are more than natural numbers even though both are infinite. It is getting very complicating when trying t order and categorize infinite sets and this would be more of a research in maths than a way of comparing functions.

---

UPDATE

It turns out you could simply prove O(n+m) equals to O(max(n,m)):

for every function F which belongs to O(n+m) this means that there are constant c and k such:

 F <= c(n+m) for every n>=k and m>=k

then also stands:

 F <= c(n+m)<= 2c*max(n,m) 

so F belongs to O(max(n,m)) and as a result O(m+n) is subset of O(max(n,m)). Now consider F belongs to O(max(n,m)) then there are constants c and k such:

 F <= c*max(n+m) for every n>=k and m>=k

and we also have:

F <= c*max(n+m)<=2c(m+n) for every n>=k and m>=k

so there is c'=2c and with same k by definition: F is O(m+n) and as a result O(max(n,m)) is subset of O(n+m). Because we proved O(m+n) is subset of O(max(n,m)) we proved that O(max(m,n)) and O(m+n) are equal and this mathematical proof proves you had totally right without any doubt.

Finally note that proving that m+n is O(max(n,m)) and max(n,m) is O(m+n) doesn't proves immediately that sets are equal (we need a proof for that) as your saying it just proves that functions have same order but we didn't examine the sets. Though it is easy to see (in general case) that if f is O(g) and g is O(F) then you can easily prove in that case the big O sets equality like we did in the previous paragraph.