3 ms·
Pretty much any standard notion of time complexity requires one to assume a random access machine, or else e.g. an array access is O(index) time.
by dooglius 2y ago
Pretty much any standard notion of time complexity requires one to assume a random access machine, or else e.g. an array access is O(index) time.
- tromp 2y agoTuring machines are still quite prevalent in complexity theory. Of course, robust classes like P and NP are invariant under various models, but also classes like DTIME and NTIME are defined for (single- or multi-tape) Turing machines [1]. [1] https://en.wikipedia.org/wiki/DTIME https://en.wikipedia.org/wiki/DTIME