Proving asymptotic notations for functions

Question

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.

Answer 1

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