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!
Answer
$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\}$?
No comments:
Post a Comment