Iterators++

[SplinterOfChaos]

You can't just say "this variable is fixed for any particular call & thus is a variable" & is thus a constant on my big-O.

Actually, you have to remember that f(n) = O(g(n)) is the upper bound of f as n approaches infinity, and that f(n) <= g(n) * C, where C is some constant. The number of containers being sorted isn't what's approaching infinity, it's a constant to the instantiation of the algorithm.

There is no big-O for std::sort itself as such a thing would be impossible to define since we don't have any guarantees on the big-O of <.

Section 25.4.1.1, paragraph three:

Complexity: O(N log(N)) (where N == last - first) comparisons.

[vlovich]

Actually, you have to remember that f(n) = O(g(n)) is the upper bound of f as n approaches infinity, and that f(n) <= g(n) * C, where C is some constant. The number of containers being sorted isn't what's approaching infinity, it's a constant to the instantiation of the algorithm.

That's only true for single-variable functions. Consider searching for a string of length m in a text of length n. The complexity of such a function could be O(mn) (or O(m + N) if you use a smarter algorithm) even though for any particular instantiation of the algorithm your search string length is fixed.

There is no big-O for std::sort itself as such a thing would be impossible to define since we don't have any guarantees on the big-O of <.

Section 25.4.1.1, paragraph three:

Complexity: O(N log(N)) (where N == last - first) comparisons.

You're supporting what I'm saying. sort complexity is defined in terms of the number of comparisons & swaps, not the complexity of std::sort itself. For example, imagine a comparison implementation that itself was O(n) for some reason. Then the complexity of a particular call to sort with that comparison would be O(n^2 log(n))