# Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?

Consider an algorithm with some running time bounded by $f(n)$ and suppose that $f(n) \in O(1/n)$. That means that there is some constant $c$ such that for sufficiently large values of $n$, it holds that $$f(n) \leq c\frac{1}{n}.$$ Clearly, for any fixed $c$ and sufficiently large $n$, the right side will be strictly less than $1$, which requires $f(n)=0$, since $f$ maps to $\mathbb{N}$. In my understanding, even an algorithm that immediately terminates, takes at least $1$ step (namely to terminate), i.e., $\forall n\colon f(n)\ge 1$. So no such algorithm can exist.

• It might also make sense to explain here why does $f$ map to $\mathbb{N}$. Sep 10, 2012 at 16:21
• It depends somewhat on your model. e.g. in some models we only care about the number of comparisons, or external memory reads, or bandwidth, or rounds of communication, etc. Depending on the model, some operations might not "count" and it would be possible to get $f(n) = 0$.
– Joe
Sep 10, 2012 at 18:18

Bucket sort's insertion sort step is O(1/n) on average.

Reference - CLRS Section 8.4

BUCKET-SORT(A)
1 n ← length[A]
2 for i ← 1 to n
3     do insert A[i ] into list B[nA[i ]]
4 for i ← 0 to n − 1
5     do sort list B[i ] with insertion sort
6 concatenate the lists B[0], B[1], . . . , B[n − 1] together in order


$T(n) = \theta(n) + \sum_{i=0}^{n−1} O(n_{i}^{2})$

Taking expectations of both sides and using linearity of expectation, we have

$E[T(n)] = \theta(n) + \sum_{i=0}^{n−1} O(E[n_{i}^{2}])$

It is proved that $E[n_{i}^{2}] = 2 − 1/n$

Hence step 5 takes $2 - 1/n$ time. Overall complexity of bucket sort is

$\theta(n) + n\cdot O(2 − 1/n) = \theta(n)$.

• Given @Peter's answer above, that doesn't sound right...
– Joe
Sep 10, 2012 at 18:15
• This example is not O(1/n), it's O(1) (or 2 to be exact). This is both according to the analysis above, where you say 2-1/n (each time step 5 is run) which is not O(1/n), and intuitively, sorting a bucket which has O(1) expected elements will take O(1) expected time. That said, creating a substep of an algorithm that runs in O(1/n) time on average is fairly straightforward. The "substep" is critical because generally you can't read the value of $n$ in $1/n$ time; you need to be in a framework where the algorithm already knows the value of $n$ it needs to act on.
– SamM
Sep 10, 2012 at 19:32
• (cont) Imagine a randomized algorithm that calls an $O(1)$ subroutine with probability 1/n. This subroutine takes a total of $O(1/n)$ average time per element. Obviously, this does not really answer the question in the affirmative (which makes sense because the answer is "no"; if an algorithm runs in $O(1/n)$ time it doesn't have time to read the input so it doesn't "know" to go faster; this is similar to Peter's argument). But it does give a case where this can happen. This sort of analysis is used in data structures (i.e. amortized rotation cost) so it's not as contrived as it may seem.
– SamM
Sep 10, 2012 at 19:37
• I checked the corresponding section (9.4) in the second edition, and the book does not say anything about running time being O(1/n). Therefore, unless the authors introduced an error in the third edition, it is your interpretation that is incorrect. Sep 11, 2012 at 17:32
• @Ankush: Heresy!! Everyone knows The Art of Computer Programming is the One True Scripture! (But even Knuth makes mistakes.) Sep 11, 2012 at 21:31

By definition, all functions (even the trivial) must perform at least 1 operation. It is impossible to perform half of a step; computers are discrete machines, and work incrementally. As such, the complexity $\Omega(1)$ is the lower time bound of all computational operations. In addition, for any operation accepting any N inputs, it must deal with at least a constant number of them at once (even if that number is zero). It's impossible to start at using one unit of space and halve that space infinitely; at some point your algorithm will reach the atomic unit of space for the computation (one bit, one electron, one string, whatever) and from that point you will use either zero or one of those atomic units, thus arriving at a constant base case. Thus, $\Omega(1)$ is also the lower space bound of all algorithms.

Now, it is possible, trivial even, for an algorithm to produce an output on that order of magnitude or cardinality. Given N elements, you can return 1/N of them (array[x] produces an output 1/N the size of the input array). But, this takes constant time (calculate the location of the element by offsetting the address of the array by the number and size of its elements, and return the bits beginning at that offset and continuing for sizeof(elementType)).