5 ms·

>As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalenc

>As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...) 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).

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

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