12

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 in o(g(n)) if for any positive constant c>0, there exists a constant n0 > 0 such that 0 <=f(n) < cg(n) , for all n>= n0.

Intuitively, if f(n) is in o(g(n)) if it is in O(g(n)), but this bound is NOT tight.

amit
  • 175,853
  • 27
  • 231
  • 333

3 Answers3

10

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.

amit
  • 175,853
  • 27
  • 231
  • 333
  • 2
    It's a matter of definition whether you consider the empty program a program or not. I'm not sure your point about f(x)=1/x being a function from R to R. It seems to me like it's not because it's not defined at 0. I don't understand the part about truncating Taylor series'... in general that changes the complexity. – Paul Hankin May 05 '15 at 11:53
  • @Anonymous The taylor series is just a comment, that shows a common usage of non real number. I see often the "tail" of the series (an*x^n + an+1* x^n+1 + ...) regarded simply as `O(x^n)`, especially when dealing with x0=0, to show that while it is there and is NOT 0, it is small enough to ignore for close enough values of x to x0. – amit May 05 '15 at 11:58
  • @Anonymous I have addressed the issue of 1/x not defined at 0 by extending the definition of `f:R->RU{U}`, since I do see a lot of occurances of this specific function in literature (one of them is mentioned in this answer), I believe this extension is valid. – amit May 05 '15 at 12:12
  • I think this answer contains too much somewhat tangential (and in places dubious) detail, perhaps juggling the ambiguous definitions that underlie the question. I had a stab at answering more concisely. – Paul Hankin May 06 '15 at 08:45
3

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).

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118
1

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.

Luka Rahne
  • 10,336
  • 3
  • 34
  • 56
  • 1
    I like your claim about "NO turing machine can have complexity of o(1)", but I cannot upvote the answer while you refer to o(1) as set of algorithms, while it's a set of *functions*. Your answer could be a very good one to the 2nd part of my answer, but fails and misleads readers about the first part of it, as o(1) is NOT a set of algorithms. – amit May 06 '15 at 08:52
  • You are right, i didn'n notice that there is no distinction between functions and algorithms. I there are also same gaps in this reasoning. – Luka Rahne May 06 '15 at 14:17