Is Big-O Notation Symmetric for f(n) and g(n)?

[dba]

Homework Statement

proof if f(n) = O(g(n)) then g(n) = O(f(n))

= stands for element of
c is some constant

Homework Equations

if f(n) <= c*g(n) then f(n) = O(g(n))

if g(n) <= c*f(n) then g(n) = O(f(n))

The Attempt at a Solution

I tried to go from the left-hand-side(LHS) to the right-hand-side(RHS) but this did not work out
if f(n) <= c_1*g(n) then g(n) <= c_2*f(n)

LHS-> f(n) <= c_1*g(n) multiply both sides by 1/c_1
1/c_1*f(n) <= g(n)... not getting to RHS, this does not work

If anyone can give me a hint what else I could do.
Thanks

 

[rasmhop]

Is this homework? If so you have read it wrong because the result is not true.

 

[dba]

mmmh. Ok the problem states:
prove that the notation is symmetric: for any function f,g,h:N→R>=0

if f(n)=θ(g(n)) then g(n) = θ(f(n))

So, I looked at the definition of Big Theta which is
if d*f(n) <= t(n) <= c*f(n) then t(n)=θ(f(n))

Thus, both conditions need to be true:
t(n) <= c*f(n) which is the definition of Big-O "if t(n) <= c*f(n) then t(n) = O(f(n))"
AND
t(n) >= d*f(n) which is the definition of Big-Omega "if t(n) >= d*f(n) then t(n) = Ω(f(n))"

So, I thought I have to proof both
if f(n)=O(g(n)) then g(n) = O(f(n)) and
if f(n)=Ω(g(n)) then g(n) = Ω(f(n))

But after reading your reply, I guess I already was wrong with this assumption

Do you have any suggestion how to start the proof for
if f(n)=θ(g(n)) then g(n) = θ(f(n)) with the definition Ω(f(n)) = O(f(n)) AND Ω(f(n))
Thank you for your reply!

 

[rasmhop]

Consider the intuitive meaning of big-O and big-Omega notation. f(n) = O(g(n)) means that f grows at most as fast as g (in an asymptotic sense). However obviously g can grow much faster. A simple example would be
f(n) = 0
g(n) = 1
for which f(n) = O(g(n)), but g(n) = O(f(n)). What you tried to prove could be intuitively understood as:
"if f grows at most as fast as g, then g grows at most as fast as f."
which doesn't really seem plausible.

Intuitively
$$f(n) = \Omega(g(n))$$
means that f(n) grows at least as fast as g.

From this we may get the idea to instead prove
"if f(n) grows at most as fast as g(n), then g(n) grows at least as fast as f(n), and vice versa"
That is prove that
$$f(n) = O(g(n))$$ implies $$g(n) = \Omega(f(n))$$
and the same thing with f and g interchanged. If you can do this, then you should be able to finish to proof of your actual exercise.

 

[dba]

Thank you. Your explanation makes it much easier to understand. I will try to proof what you said and see what I get. :-)

 

[dba]

Is this proof correct?

f(n)=O(g(n)) $\Leftrightarrow$ g(n)=Ω(f(n))
LHS → f(n)=O(g(n))→ f(n) ≤ c*g(n) → (1/c)*f(n) ≤ g(n) → g(n) ≥ (1/c)f(n) where d=1/c → g(n) = Ω(g(n)) → RHS

RHS → g(n)= Ω (f(n))→ g(n) ≥ d*f(n) →(1/d)*g(n) ≥ f(n) → f(n) ≤ (1/d)g(n) where c=1/d → f(n) = O (f(n)) → LHS


g(n)=O(f(n)) $\Leftrightarrow$ f(n)=Ω(g(n))
LHS → g(n)=O(f(n))→ g(n) ≤ c*f(n) → (1/c)*g(n) ≤ f(n) →f(n) ≥ (1/c)g(n) where d=1/c →f(n) = Ω(g(n)) →RHS

RHS f(n)= Ω (g(n))→f(n) ≥ d*g(n) →(1/d)*f(n) ≥ g(n) →g(n) ≤ (1/d)f(n) where c=1/d →g(n) = O (f(n)) →LHS

 

[rasmhop]

Yep that's fine. Though you may note that you are just doing the same thing twice with f and g interchanged so in the second part you could just refer to the first part with f and g reversed.

Also a small typo. In the third and fourth line you write
g(n) = Ω(g(n))
f(n) = O (f(n))
when you mean
g(n) = Ω(f(n))
f(n) = O (g(n))

 

[dba]

Yes, I see it. i did write is good on my paper. soory about that.

How would I express a referal to the first part with f and g reversed. Something like:
since f(n)=O(g(n)) implies that g(n)=Ω(f(n))
we can say that g(n)=O(f(n)) implies that f(n)=Ω(g(n)) ?

Thank you very much for your help!