I know that some operations are definitely constant time, such as accessing an item in a list, however there are other operations that are assumed constant time sometimes, but non-constant other times, such as multiplication.

So if we were to deal with very, very large operations, which operations would be truly constant time, or at least polynomial for exponentially large data

  • 2
    $\begingroup$ It all depends on your model of computation. On "usual computers" (modeled by Turing machines for example), multiplication (and even addition) is definitely not a constant time operation. But in other models such as BSS (Blum-Shub-Smale), it is often assumed to be a basic operation and as such run in constant time. $\endgroup$ – Amaury Pouly Dec 9 '17 at 23:02
  • $\begingroup$ hmm so what would be constant time operations on a Turing machine? Is there a list that i can see? $\endgroup$ – wjmccann Dec 9 '17 at 23:35
  • $\begingroup$ Given a reference to the head of a linked list, accessing the (i)th item in that linked list is not a constant time operation. $\endgroup$ – JimN Dec 10 '17 at 21:31

To answer this question properly, one needs two things: a model of computation and a notion of (time) complexity. Especially when talking about sub-linear complexity, the influence of the model of computation is extremely important. Starting from linear-time (and especially when dealing with polynomial time), it becomes mostly irrelevant and people avoid mentioning it. Consider addition for example:

  • Turing machine1 with classical time complexity: addition takes linear time on the size of the input because the machine has to read the inputs and that takes linear time.
  • Straight-line program(SLP) counting number of instructions: addition is in constant time because there is an instruction for that.
  • Boolean circuit with depth complexity: addition takes logarithmic time in the size of the input (using an optimized adder).

In fact Turing machines are not a very accurate model of current computers because they cannot do random accesses2 and very little can be done in constant time. This why counter machines and RAM models are more accurate, but also come with their drawbacks. Models such as SLP where addition is a constant time operation are known to be unrealistic because they can produce numbers of exponential size in the number of instructions.

When dealing with numbers, it is common to refer to "bit-complexity" and what it really means is a model that deals with bits and has random access memory. In this kind of model, addition can be done in linear time and multiplication in $O(n\log n \log\log n)$ where $n$ is the number of bits. Wikipedia has a page listing other operations.

1I am going to ignore the possible variations on the number of tapes, in this example we can consider that the two numbers are on different tapes and we have a dedicated output tape.

2Though one can argue that current computers are really only finite automata because they are finite, but this is not necessarily a useful point of view; or that computers really have logarithmic time random access in the size of the memory.


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