Proof Big-O notation property

1. Jan 27, 2012

dba

1. The problem statement, all variables and given/known data
proof if f(n) = O(g(n)) then g(n) = O(f(n))

= stands for element of
c is some constant

2. Relevant 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))

3. 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

2. Jan 27, 2012

rasmhop

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

3. Jan 27, 2012

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))

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))

4. Jan 27, 2012

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.

5. Jan 27, 2012

dba

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

6. Jan 27, 2012

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

7. Jan 27, 2012

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))

8. Jan 27, 2012

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!