3 ms·
So providing a faster sort would be a violation? The standard doesn't seem to say "or better" here, but I know that in other places it does (or least used to s
by sqeaky 10y ago
So providing a faster sort would be a violation?
The standard doesn't seem to say "or better" here, but I know that in other places it does (or least used to say something similar).
- wnesensohn 10y agoNo, f = O(n log n) means that f doesn't grow significantly faster than n log n. That is true for f = n log n, but it's also true for f = n. The "or better" is implicit by using big-O. Note that this wouldn't be true if the standard said that it has to be Θ(n log n).
- dietbacon 10y agoBig O complexity is an upper bound. If something is O(1) it's also O(n) and O(n!), since it's an upper bound.