c++11 - Is it defined to provide an empty range to C++ standard algorithms?

Question

Following on from my previous question, can we prove that the standard allows us to pass an empty range to a standard algorithm?

Paragraph 24.1/7 defines an "empty range" as the range [i,i) (where i is valid), and i would appear to be "reachable" from itself, but I'm not sure that this qualifies as a proof.

In particular, we run into trouble when looking at the sorting functions. For example, std::sort:

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

Since log(0) is generally considered to be undefined, and I don't know what 0*undefined is, could there be a problem here?

---

^{(Yes, ok, I'm being a bit pedantic. Of course no self-respecting stdlib implementation would cause a practical problem with an empty range passed to std::sort. But I'm wondering whether there's a potential hole in the standard wording here.)}

Answer 1

Big-O notation is defined in terms of the limit of the function. An algorithm with actual running time g(N) is O(f(N)) if and only if lim N→∞ g(N)/f(N) is a non-negative real number g(N)/f(N) is less than some positive real number C for all values N greater than some constant k (the exact values of C and k are immaterial; you just have to be able to find any C and k that makes this true). (thanks for the correction, Jesse!)

You'll note that the actual number of elements is not relevant in big-O analysis. Big-O analysis says nothing about the behavior of the algorithm for small numbers of elements; therefore, it does not matter if f(N) is defined at N=0. More importantly, the actual runtime behavior is controlled by a different function g(N), which may well be defined at N=0 even if f(0) is undefined.