2
$\begingroup$

The same question has been asked here

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}$

The solution given in the link hints that we can negate the definition of $ \overset{\infty}{\Omega}$ which gives us the definition of big O.

But negation of the definition of $ {\Omega}$ also gives us the same result, doesn't it?

I cannot wrap my head on how the condition of infinitely many integers makes difference rather than saying for all n greater than certain $n_0$.

Please help me understand this.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ if n is odd then ​ f(n) = 1 ​ else ​ f(n) = n ​ ​ ​ $\endgroup$ – user12859 Mar 6 '17 at 16:49
  • $\begingroup$ If the two definitions, once negated, become equivalent, they were already equivalent before the negation. Since that does not hold, you probably made some mistake when negating the definition of $\Omega$. Be very careful when negating quantifiers: in my experience, many fail at that point. $\endgroup$ – chi Mar 6 '17 at 18:17
  • $\begingroup$ I need help in negating the definition of ${\Omega}$. Negation of infinitely many integers is that there are fixed number of integers of which there will be some maximum integer say ${n_0}$ after which condition won't hold true. Negation of n greater than ${n_0}$ is again there is some maximum ${n_0}$ after which condition won't hold true. I reach the same conclusion in both cases. $\endgroup$ – user422489 Mar 6 '17 at 18:24
  • $\begingroup$ Consider the set of even positive integers. ​ ​ $\endgroup$ – user12859 Mar 7 '17 at 4:47
1
$\begingroup$

When you negate $\Omega$ you get $\stackrel{\infty}{O}$, the analog of $\stackrel{\infty}{\Omega}$. I suggest writing the definition of $\Omega$ as a first-order formula and then negating it.

To see the difference between $\Omega$ and $\stackrel\infty\Omega$, consider the functions $f(n) = n$ and $$g(n) = \begin{cases} 1 & \text{$n$ even,} \\ n^2 & \text{$n$ odd.} \end{cases}$$ You can check that $f(n) \neq O(g(n))$ and $f(n) \neq \Omega(g(n))$, whereas $f(n) = \stackrel\infty O(g(n))$ and $f(n) = \stackrel\infty\Omega(g(n))$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Got it. I was not thinking about cases where f(n) won't belong to both big Oh and big Omega. That example helped. Thanks $\endgroup$ – user422489 Mar 19 '17 at 13:36

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.