> This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1).

How about 'consistent time' or 'uniform time' for non-O(1) uses?