# Thread: 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)
$\displaystyle f(n) = \Omega(g(n))$ and $\displaystyle g(n) = \Omega(h(n))$

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

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

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

So:

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

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

RonL

#### Search Tags

omega 