Multiple Variables in Asymptotic Notation

Question

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?

• Yuval Filmus: 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.
• iRestMyCaseYourHonor: 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?
• zkutch: Answered here cs.stackexchange.com/questions/132010/…

Answer 1

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}$.)

• iRestMyCaseYourHonor: 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.