what is the running time for insertion of an element at some index of arrayList?

Question

I was wondering what is the running time for add(index,E) method of java ArrayList. According to the javadoc the running time for add operation is amortized O(1). But in the description of add(index,E) it says that.

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

So it looks like O(N). I was wondering what do we have to trade for, if running time for this operation was to make O(1). Is there any amortization work that can be done to make this operation O(1) and sacrifice running time for some other operation ?

I read that java ArrayList is backed by arrays, would changing the data structure help?

Answer 1

ArrayList has O(n) time complexity for arbitrary indices of add/remove, but O(1) for the operation at the end of the list. Closer to O(1) lookup implies may be something like a Hash Table backed data structure with index as key and element as value. Insertion again will take O(n) time because it triggers a resize.