5
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ Better, thanks! "and so O(1) would be a better description of its performance" -- I'd still argue it's the only correct "description". ;) $\endgroup$ – Raphael Nov 30 '17 at 22:48
5
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What about a $ O (1/n) + 1 $ one? $\endgroup$ – ice1000 Nov 30 '17 at 4:35
  • $\begingroup$ It is easy to prove an algorithm of O(1) but how would you prove an algorithm running in O(1/n)? $\endgroup$ – solarflare Nov 30 '17 at 4:37
  • $\begingroup$ Think about the meaning of O (1/n) + 1. It is assumed that implementations could be faster or slower by constant factors, so O (1/n) + 1 is impossible. O (1/n + 1) is possible: An algorithm that always returns zero, for example. $\endgroup$ – gnasher729 Nov 30 '17 at 7:24
  • $\begingroup$ An algorithm that always returns 0 would be {return 0} which has a complexity of O(1). $\endgroup$ – solarflare Nov 30 '17 at 22:27
  • 2
    $\begingroup$ @ice1000 $1+O(1/n) = O(1)$. $\endgroup$ – David Richerby Nov 30 '17 at 22:50
2
$\begingroup$

$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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.