3 ms·
AFAIK the STL is free to use any algorithm they want as long as it's O(n log n).
by adrianN 10y ago
AFAIK the STL is free to use any algorithm they want as long as it's O(n log n).
- niftich 10y agoThis is correct. The C++ standard specifies that sort must have a big-O complexity of n log(n). This can be seen on pdf page 925 of this working draft from 2014 [1]. [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n429...
- sqeaky 10y agoSo 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.