A colleague of mine has asked me a question: Is the set o(1) (little o notation) empty?
My question is: Is o(1) an empty set? If not, is there a program that has o(1) time complexity?
Reminder, definition of little-o by Cormen:
A function
f(n)is said to be ino(g(n))if for any positive constantc>0, there exists a constantn0 > 0such that0 <=f(n) < cg(n), for alln>= n0.
Intuitively, if f(n) is in o(g(n)) if it is in O(g(n)), but this bound is NOT tight.
The set o(1) is not empty.
It is first important to remember that f(x) is in o(g(x)) if and only if
lim_x->infinity { f(x) / g(x)} = 0
For non zero g(x)
But, more important, what is the set of candidate f(x)?
Some define it over all real functions [1], i.e. f:R->RU{U} (Where U is undefined for some values of the functions). This means, we can use any real to real function, including the function f(x)=1/x.
We can also see that g(x)=1 is a non zero function, and indeed:
lim_x->infinity { 1/x / 1} = 0
This means, o(1) includes the function f(x)=1/x, and we can conclude the set is none empty.
Knuth also refers the function g(n) = n^-1 as a valid function, and uses O(n^-1) in his explanation of big O,Omega and Theta (1976)
Others, Cormen is one of them, define the set as f:N->N, where N={0,1,...}, and this also includes f(x)=0, which again holds the condition for being o(1).[2]
There is no algorithm with complexity function T(n) in o(1)
While little o notation is defined over reals, our complexity functions for algorithms are not. They are defined over natural numbers [3]. You either do the instruction, or don't. You cannot do half of an instruction, or e-1 instruction. This means, the set of complexity functions are f:N->N. Since there is no such thing as "empty program" that has no instructions (recall that the overhead of calling it itself takes time), it even narrows this range to f:N->N\{0}.
In other words, for any complexity function of an algorithm T(n), and for all n>0, T(n)>0.
We can now go back to our formula:
lim_x->infinity { T(x) / 1} >= lim_x->infinity { 1 / 1} = 1 > 0
This shows us there is no positive natural function in o(1), and we can conclude no algorithm has a complexity function that is in o(1).
Foot Notes:
(1) If you are unsure about it, recall in Taylor series, at some point we stop adding the infinite series, and just mention it is O(x^n). The function we "hide" in this big O notation is not over the natural numbers.
(2)If we however define the set N+={1,2,...} to be the set of positive natural numbers, and o(g(n)) to be a subset of positive natural functions, o(1) is an empty set, with a proof identical to the one showing no algorithm has this complexity.
(3) Well, for average cases, the image can be a non natural number, but we'll assume worst case complexity here, though the claim can still hold for average case, since there is no empty program.
From the definition of little o follows that for this condition to meet (being o(1)),there must be algorithm that completes in arbitrary short time.
This contradicts with definition of Turing machine that requires "infinite tape marked out into squares (of finite size)". Only solution for this would be empty Turing program executing 0 instruction.
but, such program can't be build, because it would require machine, that starts in terminated state and thus can not execute any other program and is not Turing machine.
The function f(n)=0 is in o(1) and so o(1) is not empty. Because for every c>0, f(n) < c * 1.
It's a matter of opinion (or definition) whether a program's time complexity can be o(1). If you think that a program can exist with no basic operations then it would have time complexity in o(1). If you think a program can't exist with no basic operations, then it will always take at least 1 time unit no matter the input, and picking c=0.5 in the definition of little-o gives you a proof that its time complexity is not o(1).
