# Math Help - Omega

1. ## Omega

Suppose we have the following 3 functions
f(n), g(n), h(n)
such that f(n) = Omega(g(n)) and g(n) = Omega(h(n)). Must it be the case that f(n) = Omega(h(n))? Explain why or give a counterexample.

My attempt:

f(n)>= c1g(n) for all n>n1
g(n)>=c2 h(n) for all n>n2

So, f(n)>=c1 c2 for all n>min(n1,n2)

2. Originally Posted by Rola66
Suppose we have the following 3 functions
f(n), g(n), h(n)
such that f(n) = Omega(g(n)) and g(n) = Omega(h(n)). Must it be the case that f(n) = Omega(h(n))? Explain why or give a counterexample.

My attempt:

f(n)>= c1g(n) for all n>n1
g(n)>=c2 h(n) for all n>n2

So, f(n)>=c1 c2 for all n>min(n1,n2)
$f(n) = \Omega(g(n))$ and $g(n) = \Omega(h(n))$

means that there exists $n_1, n_2$ and $c_1>0, c_2>0$ such that:

$f(n) \ge c_1 g(n) \mbox{ for all } n > n_1$

$g(n) \ge c_2 h(n) \mbox{ for all } n > n_2$

So:

$f(n) \ge c_1 c_2 h(n) \mbox{ for all } n> \max(n_1,n_2)$

Hence $f(n)$ is $\Omega(h(n))$

RonL