1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 2 at 10:15
  • $\begingroup$ 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? $\endgroup$ – iRestMyCaseYourHonor Mar 2 at 11:00
  • $\begingroup$ Answered here cs.stackexchange.com/questions/132010/… $\endgroup$ – zkutch Mar 2 at 11:59
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – iRestMyCaseYourHonor Mar 2 at 12:08

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.