- #1
lee534
- 7
- 0
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!
determine the properties of each situation: reflexive, symmetric, anti symmetric, transitive, equivalence relation, and partially ordered
none
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)).
thank you!
Homework Statement
determine the properties of each situation: reflexive, symmetric, anti symmetric, transitive, equivalence relation, and partially ordered
Homework Equations
none
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)).