How is the insertion of an element into the middle of an ArrayList array determined in terms of time complexity?

In Java, inserting an element into the middle of an ArrayList has a time complexity of O(n), where n is the number of elements.

This is because ArrayList is based on a regular array. When inserting in the middle, it is necessary to:

1. Make space for the new element by shifting all subsequent elements one position to the right.
2. Insert the new element into the vacated position.

Shifting elements is an operation that requires copying about half of the array elements (average n/2), resulting in linear complexity.

Example:

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
list.add(2, 99); // insert 99 at index 2
// After insertion: [1, 2, 99, 3, 4, 5]

If inserting at the end, the complexity is amortized O(1), as shifting is not needed.