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.
Arrays are stored in contiguous memory, and this applies to Python lists as well (which are implemented as dynamic arrays under the hood).
When analyzing time complexity we generally focus on the worst-case scenario, which in this case is inserting or deleting the first element of an array, i.e. index 0.
Imagine you have a sequence of boxes filled with values, and you add one to the first index of the array, what you will need to do is shift one space to the right of all the elements that are already there, assuming that there are memory slots available. Now if you remove the first element, then you have to shift all the values to the left one unit, which again is linear time.
You're absolutely right when you analyze the last element of the array, adding or removing an element at the end is a constant time operation, as it only affects 1 element. However, when analyzing time complexity, it's important to consider the worst-case cost, which is usually what Big O notation refers to.