# Multiple Variables in Asymptotic Notation

I am trying to understand the multiple variable definition of an asymptotic notation. Particularly the definition in Wikipedia. It's also discussed in Asymptotic Analysis for two variables? but I think the answer is wrong. At least it is just corrected in the comments and and referenced to a lengthy answer. What I look for is just the answer for my confusion of the example given here. Wikipedia says,

Big $$O$$ (and little $$o$$, $$\Omega$$, etc.) can also be used with multiple variables. To define big $$O$$ formally for multiple variables, suppose $$f$$ and $$g$$ are two functions defined on some subset of $$\mathbb{R}^{n}$$.

We say $$f(\vec{x})$$ is $$O(g(\vec{x}))$$ as $$\vec{x} \rightarrow \infty$$ if and only if $$\exists M \exists C>0$$ such that for all $$\vec{x}$$ with $$x_{i} \geq M$$ $$\textbf{for some i}$$ $$|f(\vec{x})| \leq C|g(\vec{x})|$$.

... For example, if $$f(n, m)=1$$ and $$g(n, m)=n$$, then $$f(n, m)=O(g(n, m))$$ if we restrict $$f$$ and $$g$$ to $$[1, \infty)^{2}$$, but not if they are defined on $$[0, \infty)^{2}$$, This is not the only generalization of big o to multivariate functions, and in practice, there is some inconsistency in the choice of definition.

What I don't understand is, if we only look for some $$i$$, why can't we use the domain $$[0, \infty)^{2}$$? For example, if I only take the $$n$$ variable to infinity ($$i$$ is 0 in this case), then shouldn't it be fine and $$f(n,m) \in O(g(n,m))$$? Shouldn't the definition be not for some $$i$$ bur rather for all $$i$$? Do I understand the notion of for some in the wrong way?

• There is no standard definition of asymptotic notation in several variables. Wikipedia gives one such definition, you are suggesting another. None of you are wrong. – Yuval Filmus Mar 2 at 10:15
• Thanks. What I ask is, for that particular definition that uses "for some", isn't [0, inf)^2 usable for O(g) which is the example they gave on wikipedia according to their definition. Because for n -> inf f = O(g) and doesn't it satisfy the "for some i" requirement? – iRestMyCaseYourHonor Mar 2 at 11:00
• Answered here cs.stackexchange.com/questions/132010/… – zkutch Mar 2 at 11:59

## 1 Answer

Suppose that we consider $$f(n,m) = 1$$ and $$g(n,m) = n$$ as functions on $$[0,\infty)^2$$. Assume, for the sake of contradiction, that $$f(n,m) = O(g(n,m))$$. According to the definition, there exist $$M,C>0$$ such that $$|f(n,m)| \leq C|g(n,m)|$$ whenever $$\max(n,m) \geq M$$. In particular, this should hold for $$(n,m)=(0,M)$$, yet in this case $$|f(n,m)| > 1 > 0 = C|g(n,m)|$$.

The problem disappears if the domain is $$[1,\infty)^2$$. Indeed, in this case we can take $$M=C=1$$, since $$g(n,m) = n \geq 1 = f(n,m)$$ for all $$n,m \in [1,\infty)^2$$.

Perhaps the problem is with unpacking the definition. According to the Wikipedia definition, $$f(\vec{x}) = O(g(\vec{x}))$$ if there exist $$M,C>0$$ such that the following holds:

If $$x_i \geq M$$ for some $$i$$, then $$|f(\vec{x})| \leq C|g(\vec{x})|$$.

Equivalently,

If $$\max(\vec{x}) \geq M$$, then $$|f(\vec{x})| \leq C|g(\vec{x})|$$.

It should be noted that this definition is not standard, and one could think of other definitions. Two particularly natural alternatives are (i) requiring all entries of $$\vec{x}$$ to be large, and (ii) requiring the inequality $$|f(\vec{x})| \leq C|g(\vec{x})|$$ to hold for all $$\vec{x}$$.

(The second option is related to the fact that for functions $$f,g\colon \mathbb{N} \to \mathbb{N}_{>0}$$, the usual definition of $$f=O(g)$$, which is a special of the definition above, is equivalent to a definition which holds for all $$n \in \mathbb{N}$$.)

• I now understand how "for all x vectors, for some i" concept with the help of this max() explanation. It turns out what I was thinking was actually "for some vector x, for some i." Thank you very much. – iRestMyCaseYourHonor Mar 2 at 12:08