Comment by geocar

> Just because functions happen to be sets ZF does not mean sets of functions are functions. O(...) denotes a set of functions.

We can enumerate all programs up to a given length, so up to that limit all sets of functions are functions.

f(x)=O(g(x)) still makes sense in exactly this way: if g(x) is 1, then f(x) is a function that is O(1) right? How do we know g(x) is 1? Because all programs of some length that compute f(x) have that property. Of course there are longer programs that do it, and shorter programs that don't, and other programs still, but we're talking about these ones.

f(x)<O(g(x)) then says that the f(x) must be shorter than that; it isn't a member of the set.

What do you think I am missing?