How to determine the time complexity of inserting an element into the middle of an array?

Inserting an element into the middle of an array requires shifting all elements that come after the insertion point to make space for the new element.

If the array length is n, then in the worst case, approximately n/2 elements need to be shifted. The shift operation involves copying elements, which takes time proportional to the number of shifted elements.

Therefore, the time complexity of inserting an element into the middle of an array is O(n).

Example in Java:

int[] arr = new int[10];
// insert element at position pos
int pos = 5;
int newValue = 42;
// shift elements to the right
for (int i = arr.length - 1; i > pos; i--) {
    arr[i] = arr[i - 1];
}
arr[pos] = newValue;

Here, the shift loop determines the linear complexity.