Asymptotic notation between two sets of variables

Question

I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its extension to the multivariable case ($f(n, m) = O(g(n, m))$). However I don't actually understand the meaning of $f(n) = O(g(m))$ since $f$ and $g$ work with two different variables.

If for example I have that $n = O(m)$, the intuition behind this is that $m$ upper bounds $n$ but I'm not quite sure how to apply the formal definition of big O. The first idea was to use a dummy function approach by defining $f(n, m) = n$ and $g(n, m) = m$ but this does not work out well.

Another idea was to assume that both $n$ and $m$ are a function of some unknown variables that depend on the problem at hand. In this case $n = n(x_1, \ldots, x_k)$, $m = m(x_1, \ldots, x_k)$ and $n(x_1, \ldots, x_k) = O(m(x_1, \ldots, x_k))$.

Is this right? Am I missing something?

Answer 1

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:

1. There exists a constant $C > 0$ such that for all natural $n,m$, $f(n,m) \leq Cg(n,m)$.
2. There exist constant $C,N,M > 0$ such that for all natural $n,m$ if $n \geq N$ and $m \geq M$ then $f(n,m) \leq Cg(n,m)$.
3. 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 > 0$ there exists a constant $D > 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 "elided quantifier" 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>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.