Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

migrated from cstheory.stackexchange.com Nov 22 '12 at 23:48

This question came from our site for theoretical computer scientists and researchers in related fields.

marked as duplicate by Kaveh, Realz Slaw, Luke Mathieson, A.Schulz, Raphael Nov 23 '12 at 9:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer 1

up vote 2 down vote accepted

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.

Edit: I had not seen the quantum computing reference, so my answer might not be total, although I doubt it makes sense even in that context.

share|improve this answer
1  
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. –  Realz Slaw Nov 23 '12 at 0:45
    
I am aware of amortized complexity, but I do not understand what you mean by "the amortized time of computing the length of an array". Could you elaborate on this ? –  beauby Nov 23 '12 at 2:09
    
@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. –  Raphael Nov 23 '12 at 9:33
    
@Raphael maybe one can argue that you don't have to actually go through each element here. Dunno if that makes sense. –  Realz Slaw Nov 23 '12 at 11:24
1  
@RealzSlaw Still, from a Turing machine point of view, you would have to copy the answer to the output tape, which takes at least 1 operation. You'd have to do this for every array, so the amortized complexity would be constant (which it already is, without amortization). –  beauby Nov 23 '12 at 11:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.