1
$\begingroup$

I recently started learning about asymptotic notations. While I was doing practice questions (not HW) I found various question that stumped me totally. So I just want some pointers on how to go by solving these type of questions. So here is a basic question. Given the following,

If $f(n) = \Omega(h(n))$ and $g(n) = O(h(n))$ then $f(n) = \Omega(g(n))$.

How can I solve this and see if that is true or false. Here is what I have tried so far, I tried to use definitions of big-$O$ and big-$\Omega$ on $f(n)$, $g(n)$ and $h(n)$ and then combining those resulting equations to prove/disprove the outcome but I got confused.

So I need explanation of this solutions so I can make it more clear for myself. Any help would be appreciated.

$\endgroup$
1
$\begingroup$

The first thing to do is to try to develop an intuition for whether the claim is true or false. Very roughly, $f=\Omega(h)$ says that $f$ is bigger than $h$, and $g=O(h)$ says that $g$ is smaller than $h$. In both of those statements, "bigger" really means "at least as big as" and I've left off the conditions of "up to a constant factor" and "for large enough inputs".

So, if $f$ is bigger than $h$ and $g$ is smaller than $h$, is $f$ bigger than $g$? Intuitively, it ought to be. Since we've simplified, we might have gone wrong, but our intuition is that we should try to prove that the statement is true, rather than trying to find a counterexample.

Apply the definitions and you get that (try it on your own, first!)...

... there are constants $c$ and $d$ such that, for all large enough $n$, $f(n)\geq c\,h(n)$ and $g(n)\leq d\,h(n)$. Therefore, $f(n)\geq \tfrac{c}{d}g(n)$ for all large enough $n$, which is to say that $f=\Omega(g)$.

$\endgroup$
  • $\begingroup$ Thanks so much! This is exactly how I deduced and found out that this statement is true. But I got confused weather I was doing it right or not. :) $\endgroup$ – newbie Jan 14 '18 at 6:10

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.