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.
- n
^{2}is*not*in O(n): for any fixed K, when n > K you have n^{2}> 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.