Is there really a $ O(1/n) $ algorithm?

Question

What kind of algorithm can have $O(1/n)$ complexity, where $n$ is a natural number?

Or, is there any algorithm that the time it takes decreases when the data input increases?

Answer 1

No algorithm really has an $O(1/n)$ running time, but that notation might be used informally for an algorithm who's running time is really $O(m/n)$ where $m$ is large and not expected to vary. Here's an example of such an algorithm:

Given an unordered set (e.g. a hash table) containing $n$ values from the integer range $0 \le x \lt m $ (for some $ m \in \Bbb{N}^* $). (Note that $ n \le m $, as a set can't contain any duplicate values.)

We want to find the minimum value in the set as efficiently as possible.

If $n$ is much smaller than $m$, then a linear scan through the values in the set is the most efficient solution ($O(n)$).

But if $n$ is greater than $\sqrt m$, it will often be more efficient to iterate over the potential values starting with $0$ and going up, testing each one to see if it's in the set. We can of course stop as soon as we find one, since it will be the smallest one.

The expected number of tests (assuming the data is randomly distributed over the range) is $m/n$. If we consider $m$ to be a constant (as in real-world applications it will often be determined by something we can't easily change like the size of our integer data type), this seems like it would be $O(1/n)$ (with a large constant factor of $m$). And that does give an accurate description of how the performance of the algorithm changes as $n$ goes from $ \sqrt m $ towards $m$ while $m$ remains the same.

But the notation is not strictly correct. Asymptotic notation is intended to describe behavior as its variable terms go towards infinity. If an $O(1 / n)$ algorithm could run for $n$ approaching infinity, its running time would tend towards zero, but the $1 / n$ term would be dominated by constant terms (and so $O(1)$ would be a better description of its performance). For an algorithm that only makes sense on a bounded $n$, it's not correct to use asymptotic notation. For a strict asymptotic analysis, you need to consider $m$ a variable too so that both $m$ and $n$ can increase towards infinity.

I suspect that if you ever see $O(1/n)$, it's being used as an informal shorthand for $O(m/n)$.

Answer 2

Considering that even the algorithm

return 1

has $\Omega(1)$ running-time cost, it seems obvious that running-time in $o(1)$ is impossible.

Other cost measures are often equated with running time, e.g. comparisons in sorting. That makes sort of sense since, usually, we pick dominant operations that have the same $\Theta$-class as the "running time". Such a cost measure might turn out to have growth in $o(1)$ -- but then it can not be dominant!

Answer 3

An algorithm, as I understand it, can not have less than 1 step making the minimum complexity O(1). So I can't see how an algorithm can run in O(1/n) steps.

Answer 4

$1/n$ is a monotonously decreasing function. Even if it is theoretically possible that there are algorithms which become faster with larger input, this does not make sense in practice.

A monotonously falling function $f$ can always be estimated by a constant, and thus $O(f) \subseteq O(1)$.