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.

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.

• python
• time-complexity

Share Improve this question Follow edited Mar 25 at 6:47 VLAZ 29.1k99 gold badges6363 silver badges8484 bronze badges asked Mar 24 at 22:21 rararararara 30133 silver badges77 bronze badges 1

• 1 ("in case that matters" -- yes, it matters immensely; different languages implement their built-in types different ways) – Charles Duffy Commented Mar 24 at 22:56

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 2

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.