# 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$. May 20 '13 at 4:04
• See here or here.
– Raphael
May 20 '13 at 19:45
• I think there is a mistake. In the definition of $\Omega$, the inequalities hold for all real $n \geq n_0$ and not just integers $\geq n_0$. Apr 19 at 10:35

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?? 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. Jul 16 '17 at 6:00
• @Prof. Filmus, I guess $f(n) \notin \overset{\infty}{\Omega}(g(n))$ implies $f(n) \leq c \cdot g(n)$ for large enough integers $n$. To show $f(n) \in o(g(n))$, I guess the inequality needs to be proven for all $n$. Would you please help me understand this. Apr 19 at 11:28
• To show that $f(n) \in o(g(n))$, you need to show that $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$. Apr 19 at 11:40

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 Jan 14 '18 at 11:06