What is the insertion complexity of ArrayList?

The complexity of inserting into an ArrayList depends on the insertion position:

• Insert at the end: Amortized complexity O(1), as typically the element is simply added to the end of the array. When the array overflows, a memory reallocation occurs (copying to a new larger array), which takes O(n), but this happens rarely.

• Insert in the middle or beginning: Requires shifting all subsequent elements to the right, so the complexity is O(n) in the worst case.

Example:

• If you have an ArrayList of 100 elements and insert an element at position 50, elements from 50 to 99 will shift one position to the right, which takes O(n) operations.

Thus, inserting into an ArrayList is efficient only at the end, while inserting at an arbitrary position is time-consuming.