Within cryptography, yes, but in programming in general, absolutely not.
The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. It's a shame the cryptographers didn't pick a different term.
Within cryptography, yes, but in programming in general, absolutely not.
The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. It's a shame the cryptographers didn't pick a different term.
The normal usage of the phrase "constant time" predates CS by centuries, and it is much closer in usage to the crypto version than the complexity version.
Crypto uses the term "constant time" to mean same time for any input, while the general CS community uses O(1) to mean bounded time and also often uses complexity to hide log N terms. It also allows variable time, as long as it's bounded (and that sometimes allows hiding terms like log N or log log N...).
A good example is most algorithms treat addition as a constant time operation, but, for example, addition of indices for lookups is not constant time when inputs are unbounded. So if you compute an index by addition and ignore the logN time to do the addition, then you fudged. Yet this is commonplace in complexity theory, which models many basic operations as constant time when they are not for unbounded inputs.
For example, a "constant time" hash table operation, which often indexes arbitrarily large indices with addition, ignores the log N needed to add arbitrarily large indices.
Thus crypto uses the phrase in the more precise, centuries old usage.
I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. The reason for that I do not find this possible with classical computers is that no matter what you do, reading data from memory is an unavoidable variable time process.
Do not that arbitrary sized inputs here imply that the input is meaningful and must all be processed. I do not see algorithms that do not process their inputs as candidates here, such as the elsewhere stated example of even/odd test which just read a single bit. I consider an algorithm that only reads a fixed amount of information from its input to be a fixed-input algorithm, regardless of the "full" size of its input.
Of course, if you place an upper bound on the input, then you can pad in various ways, or possibly have algorithms whose execution time is inversely proportional to its input size, thus balancing itself. However, placing an upper bound also mean violating the "arbitrary" requirement entirely, thus disqualifying the algorithm.
Do note that I'd actually be quite interested if you have examples of such algorithms.
With respect, I think you may misunderstand the meaning of "constant time" in the sense of complexity theory, i.e. O(1). Accessing an element in an array of size n is a constant time operation. See: https://stackoverflow.com/questions/7297916/why-does-accessi...
EDIT: Corrected "search" to "access"
TLDR: using optics for sorting