Perhaps, but originally we weren't discussing 0, we are starting with an arbitrarily large number. This problem is exacerbated when you say:
> I disagree that increasing "exponentially"... is always faster ... Both versions have the same worst-case running time
Worst case, sure, but how do you compute average? You could take a selection of n number of integers from 0 to infinity and the number of guesses until you found the correct answer, but of course you can't do this because you can't easily get a random number to test with that is between 0 and infinity. That said, it is fairly clear that x * x is faster than 2x is faster than x+1, but you can only prove this to be true once you pick an arbitrary limit less than infinity -- and the benefits of the better algorithm are only evident as you approach infinity.
Seems like a catch 22. Perhaps there is some expert in set theory as applied within computer science that can provide the appropriate formal context for determining the better algorithm in this context.
As for O notation, it is an interesting tool but one that has no application within any realm of actual programming in which I have worked, and I have never bothered to learn it simply to dazzle people in algorithm-based interviews (perhaps because I do more nuts and bolts type work rather than optimization).