Big O Notation asymptotic relationship

Question

I cannot prove correctness/incorrectness of the implication of two functions f(n) and g(n) in Big-Oh/asymptotic notation

$$g(n) = \Omega(f(n)) ) \implies g(n) = O(n^2f(n))$$

I believe $g(n) = \Omega(f(n)) ) \implies f(n) = O(g(n))$

but not the other way around ?

Thanks for any hints!

score 1 · Answer 1 · answered Apr 26 '16 at 20:02

1

You're starting with a function $g$ which is bounded below by a function $f$. If you multiply that function $f$ by $n^2$, do you think it will necessarily be larger than $g$ afterward?

What if $f$ is much smaller than $g$?

answered Apr 26 '16 at 20:02

Antonio Vargas

24,993

Is there a way that can be proved by contradiction ? – HGO HGO Apr 27 '16 at 08:20
@HGOHGO Yes, try to come up with example functions $f$ and $g$. It's not really contradiction though, you want counterexamples. – Antonio Vargas Apr 27 '16 at 16:42

Big O Notation asymptotic relationship

1 Answers1