Your A is pretty much equivalent to \Theta. Saying f \in \Theta(g) is equivalent to saying \Theta(f) = \Theta(g).
Edit: as an aside O(f) = O(g) is also equivalent to f \in \Theta(g), and O(f) \subset O(g) is equivalent to f \in O(g).
Your A is pretty much equivalent to \Theta. Saying f \in \Theta(g) is equivalent to saying \Theta(f) = \Theta(g).
Edit: as an aside O(f) = O(g) is also equivalent to f \in \Theta(g), and O(f) \subset O(g) is equivalent to f \in O(g).
A(f) <= A(g) iff f is O(g)
Theta(g) is a set, and the most natural ordering on sets is subsetting/inclusion. However, Theta(x) is not a subset of Theta(x^2), even though x is O(x^2)! So the natural ordering on sets doesn't do what I want.It might be possible to define an ordering on Theta-classes that does what I want, though.
Edit: I just saw your comment about O. I think O might just work! So instead of remembering big-O, Theta, and Omega, I can just use
O(f) <= O(g) for f is O(g)
O(f) = O(g) for f is Theta(g)
O(f) >= O(g) for f is Omega(g)
Is that true?(I think small-o might be slightly more complicated, unfortunately. It has a more unusual definition: https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notati...)
> O(f) <= O(g) for f is O(g) > O(f) = O(g) for f is Theta(g) > O(f) >= O(g) for f is Omega(g)
>Is that true?
Yeah, I'm pretty sure that will work (haven't checked it very rigorously though). The definition of O(f) <= O(g) would simply be O(f) \subset O(g), which immediately satisfies almost all criteria (only tricky bit is proving that either O(f) is a subset of O(g) or the other way around).
For little o I think you should be able to use O(f) < O(g), using the ordering defined above.
Yes, and that's the reason why
- g \in O(f) is an upper bound on g
- g \in Omega(f) is a lower bound on g
- g \in Theta(f) is a "tight" bound on g, or both an upper and a lower bound at the same time