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?