0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Mar 14, 2021 at 4:20

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.