big o - 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.