What is the complexity of inserting into the middle of an array?
The time complexity of inserting an element into the middle of an array is O(n) (linear).
Why
An array is stored in a contiguous memory area, so adding a new element in the middle requires:
- Shifting all elements to the right of the insertion position one cell to the right, to free up space for the new element.
- Writing the new element into the freed position.
Each shift is a copy of a value from one cell to another, and there can be up to n such operations (in the worst case, if the insertion is near the start of the array).
Example
javascript
Original array: [1, 2, 3, 4, 5]
Insert 99 at position 2:
→ [1, 2, 99, 3, 4, 5]To insert 99, [3, 4, 5] had to be shifted, 3 elements.
If the array had 1,000,000 elements, almost all of them would have to be shifted.
Formally
- Best case (at the end): O(1)
- Worst case (at the start or middle): O(n)
- Average case: also about O(n/2), which asymptotically is O(n)
Summary
Inserting into the middle of an array requires shifting elements and runs in O(n). This is one reason arrays are inefficient for frequent insertions and deletions.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.