What set of primitive operations are assumed to be constant time in complexity analyses?

Question

Different set of primitive operations lead to different complexity of certain problems. For example, sorting by comparison is only O(N*log(N)) if one assumes both integer comparison and random array indexing are O(1). While this might hold for bounded N, I believe complexity analysis is, theoretically, supposed to speculate about the asymptotic growth of a function, whereas it is obvious that you can't implement constant-time comparison or array indexing for arbitrarily large values. This makes me question the theoretical merits of such complexity analyses.

My question is: when there is a literature result such as X algorithm is found to be quasipolynomial, which set of primitive operations are assumed to be constant time?

Answer 1

It depends on the "model of computation". The model of computation specifies things like what can be done in a single step and what operations are available. There are different models of computation, each of which can sometimes lead to a slightly different running time.

If the model of computation makes an important difference and the paper is being careful, it will usually mention which model of computation it is working in. Sometimes we don't care about the difference (or the difference is negligible) and then the model of computation might not be mentioned.

So, your model of computation could specify that pointers and integers (large enough to hold numbers in the range $[0,N]$) fit in a single word and can be accessed in $O(1)$ time. Or, it might specify that this takes $O(\log N)$ time and space. A circuit-centric model of computation might count the number of gates in a circuit needed to do the computation. There are many others.

One example of a model of computation is the RAM model.