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?
$\begingroup$
$\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
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
