# O(n+m) vs O(n+2m) time complexity

Are $$O(n+m)$$ and $$O(n+2m)$$ the same?

If $$m>n$$, then both complexities are $$O(m)$$. Likewise, if $$n>m$$, then they are $$O(n)$$. Is this correct?

• Since $n+m \le n+2m \le 2(n+m)$, assuming $n$ and $m$ are non-negative, $O(n+m) = O(n+2m)$ under whatever reasonable definition of $O$ for two variables, as long as it is not the case that both $n$ and $m$ are bounded. Mar 14, 2021 at 4:20

I would like to try an intuitive explanation.

Assume your algorithm works in $$2m$$ time units on your current machine. If you run it on a machine twice as fast, then it takes $$m$$ times units. As we do not know (and do not care) on which machine(s) the algorithm will run, this makes the $$2$$ factor irrelevant. This is what the big-$$O$$ notation captures, in a sense.

(In addition, if we know that $$n>m$$ then we have $$3n > n+2m$$, and so anything below $$n+2m$$ also is below $$3n$$. As big-$$O$$ deals with upper bound, this means that $$O(n+2m)$$ complexity is, in this case, in $$O(3n)$$ complexity which, as explained above, is nothing but $$O(n)$$.)

Hope this helps.

Assuming $$n, m$$ independent variables let me use definition for big-$$O$$ for multiple variables, which I discussed in Big O of multiple variables:

$$O(f(n,m)),(n,m) \to \infty$$ is set of functions $$g$$, such, that $$\exists C_g>0$$ and $$\exists M_g>0$$ such that for $$\forall \left\Vert (n,m)\right\Vert_\infty > M_g$$ holds $$g(n,m) \leqslant C_g f(n,m)$$, where $$\left\Vert(m,n)\right\Vert_\infty = \max\{n,m \}$$ based on intention to infinity by squares. It's well known Chebyshev norm or the infinity norm and is equivalent to intention to infinity by rectangles.

As case $$O(n+m) \subset O(n+2m)$$ is obvious, let me go to reverse subset direction: assume we have $$f\in O(n+2m)$$, which means $$f(n,m)\leqslant B_f (n+2m)$$ in appropriate conditions for some constant $$B_f$$. Now we need such $$C_f$$ for which holds $$B_f (n+2m) \leqslant C_f(n+m)$$. It's easy to see, that any $$C_f \gt 2 B_f$$ satisfy this condition, so $$O(n+2m) \subset O(n+m)$$, which means, that we obtain equality.

At end let me say, that if $$n, m$$ are not independent variables, then it requires more context as well as if/when we decide to consider other types of intentions to infinity such as intention to infinity by circles, by triangles etc.