O(0) would mean a complexity that tends toward zero for large input sizes. It may still take a ridiculously large amount of clock time, but you know that if you provide larger numbers tending out to infinity, asymptotically the complexity is continually decreasing. The function -- whatever it is -- becomes progressively less complex to solve the bigger the input, asymptotically reaching no complexity at all.

Not sure I agree with this at all.. that would be O(1). O(0) is only the empty algorithm. NOP is not O(0), an empty function that is actually a function is not O(0), ret 0 is not O(0), the only thing that is O(0) is nothing, the empty algorithm that is never started and never ends as it is nothing. Try to call it on the complete set of particles in the universe and it is never run, the algorithm is never started and never existed as it was erased on compile-time.

If one source contains an algorithm and another does not and they yield identical bytecode after compilation, then that algorithm is O(0).

Leaf-methods on trees where only branches have code can reasonably be described as O(0), if they are expected to be optimized out for example. Can't think of an example where it would make a difference for the final O(..) .. but I somehow suspect there might be some example where a sub-algorithm that is expected to removed would give a theoretical answer closer to reality if it was designated O(0) rather than O(1) in the analysis.

I'm going to disagree slightly with both of these. To me the most coherent definition of O(0), at least based on the definition of O I've always used (which is the same as Wikipedia's) is to say that f(x) is O(0) if and only if f(x) is the empty algorithm for values of x larger than some (finite) x0.

Similar to what frob is saying, but I don't think saying that a function tends toward having no complexity is quite strong enough, as it permits that the function f(x) may still have non-zero complexity for all values of x.

Why a special definition of O(0)? It works well with the ordinary one:

if and only if

Set g(x) identical to zero and f(x) = 0 for all x >= x0. You could then either prove or define the empty algorithm to be precisely the algorithm that takes zero time. The empty algorithm doesn't depend on anything, and in particular it doesn't depend on x, so it would take no time regardless of input. No matter what angle you approach this the result should be the same.

Right, I agree that the empty algorithm is O(0). I'm just noting that the algorithm only needs to become the empty algorithm for x>=x0 (it can have non-zero complexity for smaller values of x) but that it does need to become the empty algorithm eventually. Whether a non-empty algorithm with these properties exists is another question.