3 ms·
For equality, yes, Theta works! But I care not just about equality but about comparison. In particular, it would be nice if the "natural" ordering on A(f) had t
by rntz 10y ago
For equality, yes, Theta works! But I care not just about equality but about comparison. In particular, it would be nice if the "natural" ordering on A(f) had the property that
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_notation https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notati...)
- contravariant 10y ago>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? 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.
- z1mm32m4n 10y ago> Is that true? 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