# Relations with big oh and big theta

1. Mar 6, 2014

### lee534

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
none

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.
Reﬂexivity: 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. Mar 8, 2014

### Mugged

Do you know how to do proofs? if A then B? or A if and only if B? Does this mean anything to you?

3. Mar 8, 2014

### lee534

oh that's a good point, sorry I didn't take into account that proofs would work. thanks