CODEWITHSUNDEEP
javabig-otime-complexity
Adam Thompson
Adam Thompson

Reputation: 3516

Why is .add(i, E) big O(n) in Java ArrayList?

I'm wondering why exactly .add(i, E) is O(n) when .get(i) is O(1)? Is it because potentially n elements must be shifted over to the right after the insertion?

Upvotes: 3

Views: 161

Answers (1)

Paul Henry
Paul Henry

Reputation: 375

remember Big O notation shows the Order of magnitude of the problem not its best case solution... so yes shifting the other elements in the ArrayList (backed by an Array as Siddhartha mentions) is what causes it to be O(n).

Upvotes: 1

Related Questions