Asymptotic notation between two sets of variables
Unfortunately, there is no standard interpretation of $f(n,m) = O(g(n,m))$ in common use in computer science. Here are some possible interpretations:

There exists a constant $C &gt; 0$ such that for all natural $n,m$, $f(n,m) \leq Cg(n,m)$.
There exist constant $C,N,M &gt; 0$ such that for all natural $n,m$ if $n \geq N$ and $m \geq M$ then $f(n,m) \leq Cg(n,m)$.
Some combination of the two.


In your case, you are describing a different use of asymptotic notation. Suppose that algorithm $A$ works in time $O(n+m)$ (under the first interpretation above).
Claim. If $m = O(n)$ then $A$ works in time $O(n)$.
What this really means is the following:

For every constant $C &gt; 0$ there exists a constant $D &gt; 0$ such that if $m \leq Cn$ then algorithm $A$ works in time at most $Dn$.

The proof is quite simple. Since $A$ works in time $O(n+m)$, there exists a constant $E$ such that the running time of $A$ is at most $E(n+m)$. If $M \leq Cn$ then $E(n+m) \leq E(1+C)n$, so we can choose $D = E(1+C)$.

This kind of &quot;elided quantifier&quot; is common in theoretical computer science. For example, consider the following statement.
Claim. Some Boolean function on $n$ bits requires circuits of size $\Omega(2^n/n)$.
What this statement really means is one of the following:

There is a sequence of Boolean functions $(f_n)_{n=0}^\infty$ such that $f_n$ is a Boolean function on $n$ bits and if $M(n)$ is the minimum circuit size of $f_n$, then $M(n) = \Omega(2^n/n)$.
There is an infinite set $N \subseteq \mathbb{N}$, for each $n \in N$ a Boolean function $f_n$ on $n$ bits, and a constant $c&gt;0$, such that for all $n \in N$, every circuit for $f_n$ has size at least $c2^n/n$.

Once you get used to this sort of statement, such interpretations become automatic, though unfortunately, there is often some ambiguity and vagueness involved.

Your example of $m = O(n)$ probably comes from the world of graph theory. We say that a graph is sparse if $m = O(n)$, where $n$ is the number of vertices, and $m$ is the number of edges. Graph algorithms such as BFS and DFS run in time $O(n)$ on sparse graphs.
What this really means is that if we have a collection of graphs satisfying $m \leq Cn$ or some constant $C$, then BFS and DFS run in $O(n)$ on this collection of graphs. For example, it is known that planar graphs contain at most $3n-6$ edges. Therefore BFS and DFS run in $O(n)$ on planar graphs.