1
$\begingroup$

In CLRS, one question defines $\Omega^\infty(g(n))$ such that: $$f(n) = \Omega^\infty (g(n)) \iff \exists c \in \mathbb{R}^+ : \text{for infinitely many integers } n, 0 \leq cg(n) \leq f(n) \ .$$

My question: What does it mean by "infinitely many integers"? Does it mean $\{n : n \in \mathbb{Z}\}$ or does it just mean some infinite subset of $\mathbb{Z}$ (say, for instance, every odd positive integer)?

If the latter is true, then why is $\Omega^\infty$ even useful? I'm struggling to find out what knowing the behaviour of $f(n)$ for some arbitrary infinite scattering of integers could possibly achieve.

If the former is true, why do we care about what a function $f(n)$ does for small $n$ (i.e. for $n < n_0$)? Isn't the whole point of asymptotics that we're looking for the behaviour of functions as they approach infinity?

Can someone give a bit of context to the definition of $\Omega ^\infty$, because at the moment, it just seems a very contrived definition.

$\endgroup$
3
$\begingroup$

The phrase "for infinitely many integers" means "for an infinite set of integers". This strange definition is what you get when you negate little $o$. That is, for any two functions $f,g \geq 0$, either $f = o(g)$ or $f = \Omega^\infty(g)$. In some cases $f = \Omega^\infty(g)$ is enough to derive certain consequences, and so is a useful property.

$\endgroup$
  • $\begingroup$ I can't see the difference between $\Omega$ and $\Omega^\infty$ here. $\endgroup$ – rus9384 Jul 8 '17 at 23:09
  • 1
    $\begingroup$ Common $\Omega$ holds for all $n \n_0$. In contrast, $\Omega^\infty$ could hold only for even $n$, for example. $\endgroup$ – Yuval Filmus Jul 9 '17 at 4:32

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.