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


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++) {


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