1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

Relations with big oh and big theta

  1. Mar 6, 2014 #1
    Hi all, this is a problem that I want to start early on, but I'm not sure how to show my work for this. If i say the theorems it just feels repetitive. So I guess my question is, is using theorems enough to answer this?
    thank you!
    1. The problem statement, all variables and given/known data
    determine the properties of each situation: reflexive, symmetric, anti symmetric, transitive, equivalence relation, and partially ordered

    2. Relevant equations

    3. The attempt at a solution
    1.The relation R on the set of all real function f:N→R+ where f R g if and only if f(n) = O(g(n))
    reflexive, anti-symmetric, transitive, which means Partially ordered.
    Reflexivity: f ∈ O(f)
    Transitivity: If f ∈ O(g) and g ∈ O(h) then f ∈ O(h)
    anti-symmetry: f(n) is O(g(n)) if and only if g(n) is Omega(f(n))

    2. The relation R on the set of all real function f:N→R+ where f R g if and only if f(n) = Θ(g(n))
    reflexive, symmetric, transitive, which mean equivalence relation.
    transitivity: if f(n) is Θ(g(n)) and g(n) is Θ(h(n)) then f(n) is Θ(h(n))
    symmetry: if f(n) is Θ(g(n)) then g(n) is Θ(f(n))
    reflexive: if f(n) is Θ(f(n)).
  2. jcsd
  3. Mar 8, 2014 #2
    Do you know how to do proofs? if A then B? or A if and only if B? Does this mean anything to you?
  4. Mar 8, 2014 #3
    oh that's a good point, sorry I didn't take into account that proofs would work. thanks
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted