cormen

Question

prove that if(n)=o(g(n)) if and only if g(n)=Ώ(f(n))? it comes under transitive property

Comments

Could you please ask the question properly?

---

whether the given statement satisfies transitive property?

---

I think the question is asking is this relation valid, and the answer is no.

---

but in cormen it comes under transitive property

Answer 1

Okay, i will create some cases to make you clear:

1)f(n) = O(g(n)) if and only if g(n) = Ω(f(n))

    if g(n)=Ω(f(n)) is TRUE, means g(n) >= c_1*(f(n)) for some value of c₁>0

    then there exists some value of c₂>0 for which f(n) <= c₂ * g(n)) which is the definition of : f(n)=O(g(n)).

  example:  1 )f(n) = n²

                      g(n) = n²  

 g(n) = Ωf(n) means g(n) > = c₁ * f(n) if c₁ = 1 then the condition holds true i.e, n² >= 1* n² for every value of n.

Conversely, 

 f(n) = O g(n) means f(n) <= c₂ * g(n)  if c₂ = 1 then the condition holds true i.e   n² <=  1 * n² for every value of n.

                  2) f(n) = n

                     g(n) = n²

 g(n) = Ωf(n) means g(n) > = c₁ * f(n) if c₁ = 1 then the condition holds true i.e, n² >= 1* n for every value of n.

Conversely, 

 f(n) = O g(n) means f(n) <= c₂ * g(n)  if c₂ = 1 then the condition holds true i.e   n <=  1 * n² for every value of n.

note: c₁ and c₂ values can be altered but the conditions should be satisfied.

2)f(n) = o(g(n)) if and only if g(n) = ω(f(n))

    if  g(n) = ω(f(n)) is TRUE, means ratio of g(n) to f(n) reaches to infinity when the value of n reaches infinity. that is possible only when  g(n) >>> f(n) as n is increasing to infinity .

   now think conversely, if  very large value divided by very small value gives infinity as the n reaches infinity then what happens when very small value is divided by very large value as n reaches infinity, the ratio becomes ZERO.  (read again). which is the definition of f(n) = o(g(n)) i.e, ratio of f(n) to g(n) becomes 0 when the value of n reaches infinity. that is possible only when  f(n) >>> g(n) as n is increasing to infinity . You can try some examples by taking the limits and finding the ratio of both functions

1)f(n) = n

  g(n) n³ 

2) f(n) = log n

    g(n) = n

note : f(n) and g(n) cannot have same degree because it violates the '=' case in little oh and little omega

3)f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))

    if g(n) = Θ(f(n)) is TRUE i.e. g(n)=O(f(n)) && g(n)= Ω(f(n)) .

                                                   ⤶                                ⤷

                         f(n)=Ω(g(n)  (from 1)                   &&                   g(n)=O(f(n))       (from 2)       and these two conditions prove f(n) = Θ g(n).

You can try examples as well 

1) f(n) = n⁵

    g(n) = n⁵

2) f(n) = n¹⁰⁰⁰⁰

    g(n) = n¹⁰⁰⁰⁰

Now, coming to your case  f(n)=o(g(n)) if and only if g(n) = Ω f(n)

if g(n) = Ω f(n) is true, then g(n) >= f(n) 

but  f(n)=o(g(n)) says g(n) > f(n) 

now if suppose,  f(n) = n and g(n) = n ,

g(n) = Ω f(n) holds true but f(n)=o(g(n)) does not because when n reaches infinity ratio of f(n) to g(n) = 1 and not 0 because both functions are equal and are of same degree which disproves the condition.

pheww:D

Comments

thanks bro