This week we had a bright interviewee who claimed that array has constant search time and map has even faster than that search time. Now to me if some algorithm has O(1) time complexity the only way for another equivalent algorithm to be faster is to have a smaller constant coefficient in O(1) estimate (like one algorithm takes at most 230 primitive operations and another takes at most 50 primitive operations and is therefore faster although both have O(1) complexity).
Is it possible for an algorithm to be faster than O(1) except having a smaller coefficient in the estimate?
Best Answer
It is both reasonable and common to assume that any algorithm needs at least a positive constant amount of time for every input. For example, any useful algorithm should answer something (e.g. YES/NO or some number, string, etc.), and it is reasonable to assume that doing so takes at least some constant amount of time. Under this assumption, no algorithm can have a subconstant time complexity.
(In actual computers, this constant minimum amount of time may become smaller by advance in science and technology, but no matter how fast computers become, it is still there as a constant which does not depend on the input size.)
Vhailor comments that a hypothetical algorithm which waits 1/n seconds, where n is the input length, would satisfy the condition. The argument in the above assumes that no such algorithm exists. To justify this, I would argue that it is unreasonable to assume that a machine can wait 1/n seconds for arbitrary large n, because that would require faster and faster information processing as n grows.
Sometimes you may hear “subconstant-time operations,” but before it freaks you out, check what it really means. Usually, it means that the required time divided by some other parameter is subconstant, not that the time itself is subconstant.