Big O-Notation Proof Omega and Theta

Question

Consider the following three functions $ f,g,h: \mathbb{N{}} \rightarrow \mathbb{R} $, for which applies: $ f \in \Omega(g) $ and $ g \in \Theta(h) $. Proof or disprove formal that $f \in \Omega(h) $.

I think that it is clear that $ f \in \Omega(h) $ is valid, but I don't know how to proof it formally.

If f is growing at least as fast as g, but g grows equally fast as h, f has to grow as fast as h.

It would be great if someone could give a hint. Thank you very much!

score 2 · Accepted Answer · answered Jul 11 '16 at 19:43

2

$f \in \Omega(g)$ means there exist constant $n, c$ such that $f(x) > cg(x)$ for all $x \ge n$.

$g \in \Theta(h)$ means there exist constant $m, k, K$ such that $kh(x) < g(x) < Kh(x)$ for all $x \ge m$.

How can you relate $f(x)$ and $h(x)$ for $x > \max\{m,n\}$?

answered Jul 11 '16 at 19:43

gt6989b

54,422

I don't know. At the moment it looks to me like a contradiction. – peter87 Jul 11 '16 at 19:54
I got it thanks! – peter87 Jul 11 '16 at 20:32

Big O-Notation Proof Omega and Theta

1 Answers1