patternModerate
Is there really a $ O(1/n) $ algorithm?
Viewed 0 times
algorithmtherereally
Problem
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?
Or, is there any algorithm that the time it takes decreases when the data input increases?
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#84683, answer score: 11
Revisions (0)
No revisions yet.