1
$\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, like, $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$" and if it's the latter then what's the right way of writing this?

$\endgroup$

1 Answer 1

0
$\begingroup$

All Landau symbols are "there exists" by definition. Therefore $f(n)\in g(\Omega(h(n)))$ means simply "there exist $K_1$ such that $g(K_1h(n))\leq f(n)$ for all $n\geq n_0$.

Similarly, $f(n)\in\mathcal O(g(\Omega(h(n))))$ means "there exist $K_{0,1}$ and a function $e$ such that $f(n)\leq K_0 e(n)$ and $g(K_1h(n))\leq e(n)$ for all $n\geq n_0$.

However, I would certainly avoid such cryptic notations and write it out in words: "$f(n)\in\mathcal O(e(n))$ for some $e(n)\in g(\Omega(h(n))$."

Anyways, isn't combining of $\mathcal O$ and $\Omega$ a bit strange, since one is upper bound and one is lower bound?

$\endgroup$
3
  • $\begingroup$ Thanks but I'm not sure I agree it's so clear. Landau symbol of a function denotes a set of functions (all function satisfying the limit relation). It is natural to understand a Landau symbol of a set of functions as the set of all functions that satisfy the relation for all things in the inner set, which would lead to the "there exists for all" interpretation of nesting Landau symbols. The question is what is the standard interpretation if there is one. If you have a ref that backs it up I would love to see it. Cheers. $\endgroup$
    – egosphere
    Nov 18, 2013 at 21:14
  • 1
    $\begingroup$ I don't have a ref, but think if any function would be $o(\mathcal O(x))$ in "$\exists\forall$" interpretation ;) For me, $o(\mathcal O(x))=o(x)$, because $x\in O(x)$, but for you $o(\mathcal O(x))=\emptyset$ because $(x\mapsto0)\in O(x)$. As I said, avoid unclear notation, it cannot be useful. Just write it out as I did. $\endgroup$
    – yo'
    Nov 18, 2013 at 22:08
  • $\begingroup$ Good points. Thanks. In the $\exists\forall$ interpretation, isn't true anyway that $O(e^{-\Omega(h(n))})=e^{-\Omega(h(n))}$? Which will make my question moot because that's the form I have for $g$. Anyway thanks. $\endgroup$
    – egosphere
    Nov 20, 2013 at 18:03

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.