1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof Big-O notation property

  1. Jan 27, 2012 #1

    dba

    User Avatar

    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. jcsd
  3. Jan 27, 2012 #2
    Is this homework? If so you have read it wrong because the result is not true.
     
  4. Jan 27, 2012 #3

    dba

    User Avatar

    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!
     
  5. Jan 27, 2012 #4
    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
    [tex]f(n) = \Omega(g(n))[/tex]
    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
    [tex]f(n) = O(g(n))[/tex] implies [tex]g(n) = \Omega(f(n))[/tex]
    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.
     
  6. Jan 27, 2012 #5

    dba

    User Avatar

    Thank you. Your explanation makes it much easier to understand. I will try to proof what you said and see what I get. :-)
     
  7. Jan 27, 2012 #6

    dba

    User Avatar

    Is this proof correct?

    f(n)=O(g(n)) [itex]\Leftrightarrow[/itex] 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)) [itex]\Leftrightarrow[/itex] 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
     
  8. Jan 27, 2012 #7
    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))
     
  9. Jan 27, 2012 #8

    dba

    User Avatar

    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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof Big-O notation property
  1. Big O Notation Proofs (Replies: 0)

Loading...