time-complexity - 比较O(n + m)和O(max(n，m))的复杂度

Question

我今天有工作面试。并询问了std:set_intersection的复杂性。当我回答时，我提到

O(n + m)

等于:

O(最大(n，m))

有人告诉我这是不正确的。我尝试与以下对象显示等效项:

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

我的问题是:我真的不对吗？

Answer 1

对于所有m，n≥0，有效的是在O(m + n)中max(m，n)≤m + n→max(m，n)，并且m + n≤2max(m，n)→m + O中的n(max(m，n))。

因此O(max(m，n))= O(m + n)。

附加:如果f属于O(m + n)，则存在常数D> 0，对于m和n足够大，f(n，m)