# is there an example of an algorithm that has O(1/n)? [duplicate]

Possible Duplicate:
Complexity inversely propotional to $n$

I'm curious if anyone's come up with a problem or method as n => infinity t => 0. Are there any sort of cases found in quantum computing?

As the complexity of an algorithm is a measure of the number of operations (in a sense to be defined in each context) needed to do some computation in function of the size of some input, sub-constant complexity does not make any sense. With your exemple, $O(\frac1n)$, it means that for a sufficiently large input, the algorithm does strictly less than one operation, which in terms of Turing machines means that the initial state is accepting, which means that the corresponding Turing machine does not output anything.
• Perhaps amortized time can have $\mathcal O(1/n)$. For example "the amortized time of computing the length of an array, where the length is known, for each element in the array is $\mathcal O(1/n)$". Though ofc it seems useless. Commented Nov 23, 2012 at 0:45
• @RealzSlaw: You'd still spend time $O(1)$ for each element looking up and returning the stored quantity, so you don't have constant time for $n$ operations here but linear time. Commented Nov 23, 2012 at 9:33