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?

  • $\begingroup$ Does this help cs.stackexchange.com/q/132016 ? $\endgroup$ – zkutch Jan 20 at 15:50
  • 1
    $\begingroup$ Can you give an example of when this situation arises? $\endgroup$ – user114966 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.


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.