# Asymptotic notation between two sets of variables

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?

• Does this help cs.stackexchange.com/q/132016 ? – zkutch Jan 20 at 15:50
• Can you give an example of when this situation arises? – Dmitry Jan 21 at 2:58

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.