# алгоритм – Are there real algorithms with O(1/n) complexity?

## Question:

Are there real algorithms with O(1/n) complexity? Only nonsense like this comes to mind:

``````function test(n) {
for (i=1; i<100000/n; i++) {
dosomething();
}
}
``````

They don't even exist in theory. Because it's an upper limit.

``````O(C + 1/n) = O(C) = O(1)
``````

Where C is some constant other than 0.

And it cannot be equal to 0, since in any case we have overhead at least for getting n itself and some use of it.

Because if we do not use n at all, then the complexity obviously does not depend on it and cannot be O(1/n) . And if we use it, then we will refer to it at least once and the constant will be non-zero.

Alternative justification: imagine that there is such an algorithm, but then, if n is doubled, its execution time is halved, and if n is large enough, it should become less than one processor instruction, which is impossible.

Even in the code from the question

``````for (i=1; i<100000/n; i++) {
``````

what happens when n exceeds 100000?

We will have exactly 4 operations: assignment, division, comparison and exit from the function. This is O(1) – it is no longer able to decrease as n grows .

Scroll to Top