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 ?

  • $\begingroup$ 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$. $\endgroup$
    – Shaull
    May 20, 2013 at 4:04
  • $\begingroup$ See here or here. $\endgroup$
    – Raphael
    May 20, 2013 at 19:45
  • $\begingroup$ 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$. $\endgroup$ Apr 19, 2021 at 10:35

2 Answers 2


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$".

  • $\begingroup$ I can't understand the difference of infinitely many & for large enough n. do you know a source that can help me?? $\endgroup$ Jul 16, 2017 at 5:37
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 16, 2017 at 6:00
  • $\begingroup$ @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. $\endgroup$ Apr 19, 2021 at 11:28
  • $\begingroup$ To show that $f(n) \in o(g(n))$, you need to show that $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$. $\endgroup$ Apr 19, 2021 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$

  • $\begingroup$ @YuvalFilmus please correct me If I'm wrong $\endgroup$
    – denis631
    Jan 14, 2018 at 11:06

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.