Is the time complexity of the empty algorithm O(0)?

Solution 1:

From Wikipedia:

A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

From this description, since the empty algorithm requires 0 time to execute, it has an upper bound performance of O(0). This means, it's also O(1), which happens to be a larger upper bound.

Edit:

More formally from CLR (1ed, pg 26):

For a given function g(n), we denote O(g(n)) the set of functions

O(g(n)) = { f(n): there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n₀ }

The asymptotic time performance of the empty algorithm, executing in 0 time regardless of the input, is therefore a member of O(0).

Edit 2:

We all agree that 0 is O(1). The question is, is 0 O(0) as well?

Based on the definitions, I say yes.

Furthermore, I think there's a bit more significance to the question than many answers indicate. By itself the empty algorithm is probably meaningless. However, whenever a non-trivial algorithm is specified, the empty algorithm could be thought of as lying between consecutive steps of the algorithm being specified as well as before and after the algorithm steps. It's nice to know that "nothingness" does not impact the algorithm's asymptotic time performance.

Edit 3:

Adam Crume makes the following claim:

For any function f(x), f(x) is in O(f(x)).

Proof: let S be a subset of R and T be a subset of R^* (the non-negative real numbers) and let f(x):S ->T and c ≥ 1. Then 0 ≤ f(x) ≤ f(x) which leads to 0 ≤ f(x) ≤ cf(x) for all x∈S. Therefore f(x) ∈ O(f(x)).

Specifically, if f(x) = 0 then f(x) ∈ O(0).

Solution 2:

It takes the same amount of time to run regardless of the input, therefore it is O(1) by definition.

Solution 3:

Several answers say that the complexity is O(1) because the time is a constant and the time is bounded by the product of some coefficient and 1. Well, it is true that the time is a constant and it is bounded that way, but that doesn't mean that the best answer is O(1).

Consider an algorithm that runs in linear time. It is ordinarily designated as O(n) but let's play devil's advocate. The time is bounded by the product of some coefficient and n^2. If we consider O(n^2) to be a set, the set of all algorithms whose complexity is small enough, then linear algorithms are in that set. But it doesn't mean that the best answer is O(n^2).

The empty algorithm is in O(n^2) and in O(n) and in O(1) and in O(0). I vote for O(0).