What is the time complexity of deleting from an array?
The time complexity of deleting from an array depends on where the element is deleted from: the end, the start, or the middle.
1. Deleting from the end of an array
- The last element is simply removed.
- Nothing needs to be shifted. Complexity: O(1), constant time.
2. Deleting from the start or middle of an array
- After the deletion, a "hole" forms.
- All elements to the right of it need to be shifted left to fill the empty spot.
For example:
javascript
[1, 2, 3, 4, 5]
delete 2 → [1, 3, 4, 5][3, 4, 5] get shifted, 3 elements.
In the worst case (if the first element is deleted), almost the entire array has to be shifted.
Complexity: O(n), linear time.
3. Formally
| Deletion type | Complexity |
|---|---|
| From the end | O(1) |
| From the start or middle | O(n) |
4. Why
An array is a contiguous block of memory, so an element cannot be "cut out" without shifting the rest. This is how it differs from a linked list, where deletion by reference runs in O(1).
Summary:
Deleting from the end of an array is fast (O(1)), from the middle or start it's slow (O(n)), because it requires shifting the remaining elements.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.