Is it ever possible to have Big O less than O(1)? [duplicate]

Question

Possible Duplicate:
are there any O(1/n) algorithms?

Is it ever possible for your code to be Big O less than O(1)?

Answer 1

O(1) simply means a constant time operation. That time could be 1 nanosecond or 1 million years, the notation is not a measure of absolute time. Unless of course you are working on the OS for a time machine, than perhaps your DoTimeTravel( ) function would have O(-1) complexity :-)

Answer 2

Not really. O(1) is constant time. Whether you express that as O(1) or O(2) or O(.5) really makes little difference as far as purely big O notation goes.

As noted in this question, it is technically possible to have an O(1/n), but that no real-world useful algorithm would satisfy this (though some do algorithm's do have 1/n as part of their algorithmic complexity).

Answer 3

The only thing that would take less than O(1) (constant time) would be an operation that did absolutely nothing, and thus took zero time. But even a NOP usually takes a fixed number of cycles...