A few undocumented time complexities

[AljoschaMeyer]

A couple of time complexities that are left unspecified:

• next() for the iterators of OrdSet and OrdMap (O(1)* ?)
• OrdSet::get_min (O(log n) ?)
• OrdSet::get_max (O(log n) ?)

Should I make a PR, or is it easier for you to just add those yourself?

For functions that operate on multiple data structures (e.g. OrdSet::is_subset), does the "n" in the time complexities refer to the size of the smaller or the larger structure?

[AljoschaMeyer]

Looking at the implementation of OrdSet::is_subset in particular, the given complexity of O(n log n) technically isn't correct, it is O(n log m) where n is the length of self and m the length of the other argument.

So there can be settings where foo.is_subset(&bar) is less performant than !bar.is_subset(&foo), which seems somewhat surprising. By comparing the lengths of the two arguments, it would be possible to always do the more efficient version. This is a bad example since a further optimization could directly return false if other is longer than self, but the general idea probably applies to a few other functions too.

[bodil]

I'll be the first to admit the implementations of some of the higher level functions haven't received as much attention to performance as the low level ops. is_subset is a great example of that.

[bodil]

I've implemented the early return you suggested, but I can't see a way to distinguish between foo.is_subset(&bar) and !bar.is_subset(&foo), as is_subset has no way in this case of knowing whether its return value is going to be inverted, so it can't very well optimise for it. Please correct me if I'm wrong.