Relations with big oh and big theta

In summary, the conversation discusses determining the properties of given situations, including reflexivity, symmetry, anti-symmetry, transitivity, equivalence relation, and partially ordered. The participants also discuss the use of theorems in answering these questions and how proofs can be used to show work.
  • #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!

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)).
 
Physics news on Phys.org
  • #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?
 
  • #3
oh that's a good point, sorry I didn't take into account that proofs would work. thanks
 

FAQ: Relations with big oh and big theta

1. What is the difference between big oh and big theta?

Big oh and big theta are notations used in computer science to describe the time complexity of an algorithm. Big oh represents the upper bound of the worst-case scenario, while big theta represents both the upper and lower bounds of the algorithm's running time.

2. How are big oh and big theta related?

Big oh and big theta are related in that big theta is a more precise notation than big oh. While big oh only represents the upper bound, big theta represents both the upper and lower bounds, giving a more accurate estimation of the algorithm's time complexity.

3. When should I use big oh versus big theta?

Big oh is generally used when we only care about the worst-case scenario of an algorithm's running time. Big theta is used when we want to consider both the best-case and worst-case scenarios, giving a more comprehensive understanding of the algorithm's time complexity.

4. Can big oh and big theta be used interchangeably?

No, big oh and big theta cannot be used interchangeably. While they both describe the time complexity of an algorithm, they represent different aspects of it. Big oh represents the upper bound, while big theta represents both the upper and lower bounds.

5. How can big oh and big theta help in algorithm analysis?

Big oh and big theta notations provide a way to analyze and compare the efficiency of different algorithms. By understanding the time complexity of an algorithm, we can make informed decisions about which algorithm to use for a given problem, and optimize our code for better performance.

Back
Top