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();
}
}
Answer:
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 .