Skip to main content

What is the complexity of inserting an element into the middle of an array?

AlgorithmsJunior~2 min read
Suggest an edit

Short answer

Inserting an element into the middle of an array with contiguous storage (a static array, a dynamic array, JS Array, C++ vector, Java ArrayList) has time complexity O(n) and O(1) extra memory. The reason is the need to shift every element to the right of the insertion position.

Detailed explanation

Why O(n):

  • An array stores elements in adjacent memory. To free up a "hole" in the middle, every element to the right of position i (there are k of them) must shift by one position: that is k moves, and in the worst case k ≈ n.
  • Even if a dynamic array has spare capacity and does not reallocate, shifting the elements is still required, so inserting into the middle is still O(n).
  • In terms of memory, the algorithm needs O(1) extra memory (aside from a possible rare reallocation on capacity overflow, which copies all n elements and by itself costs O(n)).

Boundaries and special cases

  • Inserting at the start: O(n) (shifting every element).
  • Inserting at the end: amortized O(1) when spare capacity is available; without it a reallocation happens, O(n).
  • A sorted array: finding the position with binary search is O(log n) + the O(n) shift, O(n) in total.
  • An exact estimate via k: if there are k elements to the right of the insertion position, the time is Θ(k). On average, at a uniform position k ≈ n/2, but the asymptotics stay O(n).

Comparison with other structures

  • A linked list: inserting at an already-found node is O(1), but index access and finding the position is O(n); worse locality and cacheability.
  • A deque: fast insertions at the ends, but inserting into the middle is usually also O(n).
  • Specialized structures (gap buffers, ropes, B-trees, list-of-vectors) can improve middle insertions at the cost of other trade-offs, but a plain array cannot.

Practical notes

  • If you need many middle insertions, an array is not the best structure. Consider a structure with cheaper insertions, or change the algorithm (accumulate changes and apply them in a batch).
  • If insertions are rare and index-based reads matter, an array remains the optimal choice.

Code examples

JavaScript (Array):

js
// Inserting into the middle is O(n) because of the element shift const arr = [1, 2, 3, 4, 5]; const index = Math.floor(arr.length / 2); // insertion position const value = 99; arr.splice(index, 0, value); // → [1, 2, 99, 3, 4, 5]

C++ (std::vector):

cpp
#include <vector> #include <cstddef> int main() { std::vector<int> v{1, 2, 3, 4, 5}; std::size_t index = v.size() / 2; int value = 99; // O(n): moving/copying the elements to the right of index v.insert(v.begin() + index, value); return 0; }

Short Answer

Interview ready
Premium

A concise answer to help you respond confidently on this topic during an interview.

Suggest an edit