What is O(0)

If you have ever taken a course in algorithms or data structures you’ll have seen big-O notation. For example you’ll know that a bubble sort runs in O(n²) time and merge sort in O(n log n) time. Maybe you have been explained that with big-O adding and multiplying by constants doesn’t matter, so O(1000n+1000) is the same as O(n). What, then, is O(0)?

You could argue that O(0) is the same as 0(1) because “constants don’t matter”, but you would be wrong. To see what it is we have to go back and look at how big-O is defined:

In English, O(f(n)) is the set of functions that grow no faster than a constant times f(n). In mathematical terms, a function g(n) is in O(f(n)) if and only if you can find two constants, K and N, such that |g(n)| ≤ K |f(n)| for every n greater than N.

In computer science n is usually the number of items to be processed, so the domain of the functions is the set of positive integers.

Examples:

  • O(1) is the set of functions that are bounded by a constant:
    • All constant functions c are in O(1): choose K=c and N=0.
    • 1000/n is in O(1): choose K=1 and you get 1000/n ≤ 1 for all n > N=999.
    • sin(n) is in O(1): choose K=1, and you get |sin(n)| ≤ 1 for all n
  • O(n) is the set of functions that grow at most linearly:
    • n+1000 is in O(n): choose K=2, and you get n+1000 ≤ 2n for all n > N=999.
    • 1000n+1000 is in O(n): choose K=2000, 1000n+1000 ≤ 2000n for all n > N=0.
    • n2 is not in O(n): for any fixed K, when n > K you have n2 > Kn, so no choice of K and N exists.
    • log n and sqrt(n) are in O(n): choose K=1.

Functions like 1000/n are hard to come by in algorithm analysis; when does a program terminate in less time when given more input? It may happen though: consider an automatic memory management system. Giving more memory while the load stays constant makes the job easier.

What is O(0) then? Let’s see: a function f(n) is in O(0) if and only if there are constants K and N such that |f(n)| ≤ K·0=0 for each n > N. In English, O(0) is the set of functions f(n) whose value eventually drops to exactly 0. Examples:

  • The constant function 0 is obviously in O(0). There are no other constant functions in O(0).
  • The binomial coefficient function n-choose-k is 0 for all k > n, so f(k)=C(n,k) is in O(0) for all n
  • 1000/n never becomes exactly 0 so it’s not in O(0). floor(1000/n) is 0 for n>1000, so it’s in O(0).

Hopefully this clears the confusion.