What is complexity of O(1/n) compared to O(n)?

Question

Is O(1/n) faster growing than O(1)? I am studying time complexity and saw O(1/n) being compared to O(n) as one of my exercise questions, and I had never seen that before. Not sure how to deduce the answer to this question.

Answer 1

A complexity of O(1/n) would means that the more data you process, the faster is the algorithm... Quite difficult to believe, for first, and second let's do maths: the limit of 1/x when x goes to +INF is zero...

The algorithm would resolve instantly the problem, then? Hey, let's forget about quantum computing, we found something better! :)

Stop joking: such a complexity doesn't exist. Because 1/n is a decreasing monotonic function. Complexities are increasing monotonic functions - at best, it's O(1), meaning a constant time whatever the data quantity is. It's not even a so common complexity for an algorithm, in fact, even if it's quite frequent for certain operations / manipulations.

For example, retrieving the head of a standard linked list is indeed O(1), even if the list is empty or if it contains all possible data of Universe (if it was storable...), because list's head is what is stored to access it. It's the same for all operations involving only exchanging pointers/handles exclusively, all direct accesses (like the [] operator of most arrays), etc. but most algorithms don't have such a nice complexity.

But even a simple (deep) copy is O(n)... Most researchs in a storage are in O(log2(n)). Most sorts are in O(n.log2(n)). Most cross-comparisons are in O(n²). All these functions are (strictly) increasing. All these functions tend to infinity when n also tends to infinity.