Variations of Omega and Omega infinity

Some authors define $\Omega$ in a slightly different way: let’s use $\overset{\infty}{\Omega}$ (read “omega infinity”) for this alternative definition. We say that $f(n) = \overset{\infty}{\Omega}(g(n))$ if there exists a positive constant $c$ such that $f(n) \geq c\cdot g(n) \geq 0$ for infinitely many integers $n$, whereas the usual $\Omega$ requires that this holds for all integers greater than a certain $n_0$.

Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically nonnegative, either $f(n) = O(g(n))$ or $f(n)= \overset{\infty}{\Omega}(g(n))$ or both, whereas this is not true if we use $\Omega$ in place of $\overset{\infty}{\Omega}$.

I am trying learn Algorithms. But I am unable to prove this. Can the experts help me ?

• Try to use the definitions, keeping in mind that for every property $P$, either $P$ holds for infinitely many integers, or $P$ does not hold for almost all integers. Observe that $\Omega^\infty$ is the negation of $O$. – Shaull May 20 '13 at 4:04
• See here or here. – Raphael May 20 '13 at 19:45

Hint: If $f(n) \notin \overset{\infty}{\Omega}(g(n))$ and $g(n)$ is asymptotically non-negative, then for all positive constants $c$, $f(n) \leq c \cdot g(n)$ for large enough $n$. This follows by ignoring the condition $c \cdot g(n) \geq 0$ and negating the definition of $f(n) \in \overset{\infty}{\Omega}(g(n))$. In fact, this way you get the stronger result that either $f(n) \in \overset{\infty}{\Omega}(g(n))$ or $f(n) \in o(g(n))$ (but not both).

Further hint: You can start by showing that the negation of "$P(n)$ for infinitely many $n$" is "$\lnot P(n)$ for large enough $n$".

• I can't understand the difference of infinitely many & for large enough n. do you know a source that can help me?? – Fatemeh Karimi Jul 16 '17 at 5:37
• I suggest a good grounding in set theory and formal logic. Something holds for all large enough $n$ if there exists $n_0$ such that it holds for all $n\geq n_0$. It holds for infinitely many $n$ if the set of $n$ for which it holds is infinite. – Yuval Filmus Jul 16 '17 at 6:00

I can give you an example so that you can better understand $\overset{\infty}{\Omega}(g(n))$. Imagine a binomial heap. The insert operation is $O(logN)$, but is it ${\Omega}(logN)$?

In cases when we have tree ranks of 4-3-2-1-0 and inserting a tree with rank 0 will be a ${\Omega}(logN)$ operation. But inserting a tree with rank 0 on the resulting heap from the previous operation (heap with having tree rank of 5) will be a $O(1)$ operation, since only pointers should be added and no extra merge work is necessary.

This is the essential difference between ${\Omega}$ and $\overset{\infty}{\Omega}$. For example the binomial heap insert operation is $\overset{\infty}{\Omega}(logN)$ for set of $n = \{{1,3,7,...,2^k - 1}\}$. It doesn't state that when $n \geq n_0$ the complexity is ${\Omega}(logN)$ but rather for some infinite set of n, but not for all $n \geq n_0$

• @YuvalFilmus please correct me If I'm wrong – denis631 Jan 14 '18 at 11:06