7
$\begingroup$

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 ?

$\endgroup$
  • $\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 '13 at 4:04
  • $\begingroup$ See here or here. $\endgroup$ – Raphael May 20 '13 at 19:45
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I can't understand the difference of infinitely many & for large enough n. do you know a source that can help me?? $\endgroup$ – Fatemeh Karimi Jul 16 '17 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$ – Yuval Filmus Jul 16 '17 at 6:00
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ @YuvalFilmus please correct me If I'm wrong $\endgroup$ – denis631 Jan 14 '18 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.