-1
$\begingroup$

I am doing homework to practice for my midterm exam and cannot answer this question. I need to decide whether or not this statement is true of false and either give a proof or counter example.

For this particular question, I am leaning more towards saying it is false as the question does not really follow the definition of Big Omega. However, how do I come up with a counterexample for this? Can anyone show me how to do this question?

Let $g$ and $h$ be any functions from $\mathbb{N}$ to $(0,\infty)$. Then $g(n)\in\Omega(h(n))$ implies there is some $N\in\mathbb{N}$ such that $g(n)\geq h(n)$ for all $n\geq N$.

Any help would be much appreciated.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Where does it differ from the definition, and how could you use this to your advantage? $\endgroup$
    – Tom van der Zanden
    Jan 24, 2015 at 19:02
  • $\begingroup$ Can you elaborate please? $\endgroup$
    – masonry
    Jan 25, 2015 at 0:00

1 Answer 1

Reset to default
2
$\begingroup$

The definition of $\Omega$ says that $g$ and $h$ might differ additively or multiplicatively by any constant. So a counter example could be:

$g(n) = n$

$h(n) = 2n$

$\lim\limits_{n \rightarrow \infty} \frac{g(n)}{h(n)} = \frac{1}{2} > 0$, hence $g \in \Omega(h)$. But obviously, $h(n) > g(n)$ for all $n > 0$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can you add more to your answer? I am a bit confused by what you did. Why did you assume g is an element of omega(h)? $\endgroup$
    – masonry
    Jan 25, 2015 at 0:05
  • $\begingroup$ I wrote a short explanation of that in my answer using the limes definition. You could also use the definition using a constant c and some $n_0$ with c=2. $\endgroup$
    – Andreas T
    Jan 25, 2015 at 0:06
  • $\begingroup$ What is the limes definition? Are you able to show how to do it with the definition? $\endgroup$
    – masonry
    Jan 25, 2015 at 0:08
  • $\begingroup$ You can find the definition using the limit of the fraction on Wikipedia or other sources as it is quite common. If you want the argument use the definition you learned, you should tell what that definition is. $\endgroup$
    – Andreas T
    Jan 25, 2015 at 0:16
  • $\begingroup$ thank you, still not completely sure however $\endgroup$
    – masonry
    Jan 25, 2015 at 0:17

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.