I was reading a bit on DS/A and found this cheat sheet on Leet Code.. Add or remove element from arbitrary index: O(n) Access or modify element at arbitrary index: O(1) Intuitively I would think they would both be O(n). Why is one O(1) and the other O(n)? Why is adding or removing an element linear, while accessing or modifying an element constant? Does it have to do with re-indexing the array? Would adding or removing the last element of an array be O(1) since you wouldn't be adjusting the index of that array. Assume we're talking about Python here in case that matters for this specific question. Continue reading...
