I don't even know if this is the right place to ask this this...but how will Big O be with quantum computers? More specifically, will the worst case always be constant? If yes, how will this change our understanding of current algorithms? For example, will this mean that the difference between an algorithm running at Big O(2^n) and another running at Big O(n^2) in traditional computers be insignificant in a quantum computer? Would time complexity even be an issue with quantum computers? This might have a very obvious answer but I don't know the answer (and I'm really am curious).


1 Answer 1


Big-O has nothing to do with quantum computers. This should be obvious by the fact that Big-O notation was introduced in 1894, long before we had any knowledge of quantum theory … or computers for that matter.

Big-O is simply a convenient notation for classifying growth rates of functions. Big-O doesn't care how you interpret those functions.

So, the definition of Big-O will not change for quantum computers for the simple reason that its definition has nothing to do with computers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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