I am with you on the point about order of magnitude but I don’t understand what you mean by log n being smaller than all positive real numbers. We are talking about asymptotics, since we are talking about O(f(n)) for some function f, right? Doesn’t log n go to infinity then since n goes to infinity?
Mostly we worry about algorithms that can run in polynomial time. It's easy to show that when m < n, xᵐ = o(xⁿ), and that when a polynomial's degree is n, the whole polynomial is O(xⁿ), and this leads us to divide up the polynomial-runtime space according to the degree of a representative polynomial. It's very normal to talk about "linear" time requirements -- meaning ϴ(x¹), "constant" requirements [ϴ(x⁰)], "quadratic" requirements [ϴ(x²)], "cubic" requirements [ϴ(x³)], etc. (OK, it's less common to talk about higher degrees, but the concept stays relevant there.)
So once you're thinking that way, you can ask where the function f(x) = log x belongs. It isn't a polynomial, but it is asymptotically limited by polynomials and so it's present within the polynomial-runtime space. If you represented the growth rate of the function f(x) = log x by a polynomial approximation, F(x) = xᵏ, what would the value of k be?
The answer is that k must be a positive value that is greater than zero but less than all positive real numbers, an infinitesimal. If you're calibrated against polynomials, a logarithmic time requirement is "not constant, but so close to being constant that it's impossible to see the difference".
