Let f(x), g(x) and h(x) be function which of following statement is false?

Question

Let $f(x),g(x)$ and $h(x)$ be functions which of the following statement is false?

a).   if $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$ then $f(x)$ is $O(h(x))$.

b).  if $f(x)$ is $\Omega(g(x))$ and $f(x)$ is $\Omega(h(x))$ then $g(x)$ is $\Omega(h(x))$

c). Both $(a)$ and $(b)$

d). Neither $(a)$ nor $(b)$

I mean according to me , option (a) is correct , right ? by the rule of transitivity .

Please correct me , if I am wrong.

Comments

only a is correct becoz in option b its given

f(x) = Ω(g(x)) i.e. f(x) >= g(x)  ...........(1)
f(x) = Ω(h(x)) i.e. f(x) >= h(x) ...........(2)

so we cant tell the relation between g(x) and h(x)

therefore a is right

Answer 1

yeah that's right , option (a) is correct

Answer 2

A.
f(x) = O(g(x)) i.e. f(x) <= g(x)  ...........(1)
g(x) = O(h(x)) i.e. g(x) <= h(x) ...........(2)

from (1) and (2),
f(x) <= g(x) <= h(x)
f(x) = O(h(x)) 


B.
f(x) = Ω(g(x)) i.e. f(x) >= g(x)  ...........(1)
g(x) = Ω(h(x)) i.e. g(x) >= h(x) ...........(2)

from (1) and (2),
f(x) >= g(x) >= h(x)
f(x) = Ω(h(x)) 

both are true..

TRANSITIVITY holds for O, Ω as well..
PS : in case of small O & Ω only reflexivity & Symmetricity faiils.

Comments

The worst problem in GATE- you should read the question carefully :O

Answer 3

There is no transitive rule here..

Let f(n) = n^4

       G(n) = n^2

and h(n) = n^3

So here both first conditions given in problem satisfy but the condition g(n) € omega o (h(n) ) fails