3
$\begingroup$

I want to express the following statement about a function $f(n)$: there exists $f_\Omega\in\Omega(h(n))$ such that $f\in O(g(f_\Omega(n))$. What's the correct notation for this? Is it $f\in O(g(\Omega(h(n))))$? Or does that notation mean that $f\in O(g(f_\Omega(n))$ for all $f_\Omega\in\Omega(h(n))$?

For example, take $f(n)=2^{-\alpha n}(n^4+n^2+\log(n))$ for $\alpha>0$. Such a function has that there exists $f_\Omega\in\Omega(n)$ (take $f_\Omega(n)=\alpha n/2$ for example) such that $f\in O(2^{-f_\Omega(n)})$. I want a nice succinct way to say this that stresses the important part (the exponential) and without mentioning the constant $\alpha$ as it is subject to change. I was thinking that this does it: $2^{-5n}(n^4+n^2+\log(n))\in O(2^{-\Omega(n)})$. But I'm not sure if this is "there exists $f_\Omega$" or "for all $f_\Omega$" (which would mean $f$ is eventually zero?) and if it's the latter then what's the right way of writing this?

$\endgroup$
7
  • 4
    $\begingroup$ In your example, just $f(n)=2^{-\Omega(n)}$ is fine. There is no need for the outer $O$, and while people abuse asymptotic notations in all kinds of ways as long as the intended meaning is reasonably clear, I can’t remember seeing two of them nested like this. $\endgroup$ Nov 18, 2013 at 16:34
  • $\begingroup$ Having said that, I would interpret $f\in O(g(\Omega(h(n))))$ the way you want, on the principle that if $X$ is a set of functions in one variable (like $\Omega(h)$), then $g(X)$ can stand for $\{g\circ g':g'\in X\}$. $\endgroup$ Nov 18, 2013 at 16:40
  • $\begingroup$ I'd like point to [this paper](people.cis.ksu.edu/~rhowell/asymptotic.pdf) that discusses the ambiguities in big-O notation for functions of multiple variables. The relevant part of it is the discussion of the desired properties of big-O notation. In particular, neither "exist" not "all" interpretation correspond to our intuition of what big-O should mean for functions of multiple variables. Although this is not the answer to your question perhaps the consideration involved in choosing the meaning of big-O notation would be useful. $\endgroup$
    – Michael
    Nov 18, 2013 at 16:49
  • $\begingroup$ I read Howell’s paper, and while I agree that it wouldn’t hurt if people were more careful and explicit when using asymptotic notation for multivariate functions, I couldn’t help the feeling he’s trying to be intentionally obtuse. There is a perfectly natural meaning one can give to $g(n,m)=O(f(n,m))$ for positive integer functions $f,g$, namely that there exists a constant $c$ such that $g(n,m)\le cf(n,m)$ for all $n,m\in\mathbb N$. This agrees with the univariate case, and generally fits the expectation of those who employ such notation, though it violates Howell’s conditions. $\endgroup$ Nov 18, 2013 at 17:07
  • $\begingroup$ My view is that asymptotic notation such as $O()$ or $\Omega()$ is basically a more sophisticated version of more familiar multi-valued notations, such as $\pm$, with $f(n) = O( g( \Omega( h(n) ) )$ being interpreted much like $x = \pm g(\pm y)$ would, namely that there exists a choice of both signs which makes the identity valid. (Ignore for the moment the fact that one does often want to force the $\pm$ signs to agree (and for $\mp$ to denote the opposite sign), but this is not the default convention and usually has to be stated explicitly.) $\endgroup$
    – Terry Tao
    Nov 18, 2013 at 17:23

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.