Time Complexity of Dynamic Arrays

Question

I am a bit confused about time complexity of Dynamic Arrays. In this article here it states that the time complexity of insertion and deletion of Dynamic Array is O(n). I wanted to know why that is the case for insertion and deletion of dynamic array.

My understanding of why the insertion of Dynamic Array might be O(n) is because once an element is inserted the other elements need to be moved back and that is O(n). However I read somewhere else the reason for this is because in case you run out of space then extra space is reallocated the previous items copied and pasted into the new memory location.I wanted to know which reasoning is correct. Also my reasoning for an array having a time complexity of O(n) for deletion is that once an element is deleted other elements are moved forth to cover the deleted items space.However again the article gives another answer and states that since searching is O(n) in Dynamic array thus deleting is O(n) in dynamic array since an element is searched before its deleted. I would appreciate it if someone could clarify this confusion. Thanks.

Solution

My understanding of why the insertion of Dynamic Array might be O(n) is because once an element is inserted the other elements need to be moved back

Correct.

Also my reasoning for an array having a time complexity of O(n) for deletion is that once an element is deleted other elements are moved forth to cover the deleted items space.

Correct.

However I read somewhere else the reason for this is because in case you run out of space then extra space is reallocated the previous items copied and pasted into the new memory location.

I think you're confusing something here. Maybe you are thinking about what happens if you insert at the end and the array overflows. In that case you also have to copy the whole array to a new, larger location. But the cost for this can be charged to the insertions at the end that must have happened for this situation to occur. So insertion at the end is "amortized O(1)".

The exact same reasoning works for deletion.

To summarize: Insertion/deletion at position k of an array has amortized complexity O(n - k). In particular, insertion/deletion at an arbitrary position is O(n) and insertion/deletion at the end is O(1).

However again the article gives another answer and states that since searching is O(n) in Dynamic array thus deleting is O(n) in dynamic array since an element is searched before its deleted

Searching has nothing to due with insertion/deletion. When considering insertion/deletion cost, you usually assume that you already know the position where you want to insert/delete.

Comments

[chris]

Be careful to avoid mixing insertion/deletion anywhere with insertion/deletion at the end for dynamic arrays. It makes a difference.

[juanchopanza]

And don't add searching into the mix. Look-up by index is O(1). Searching is a different matter.

[Rajeshwar]

Thanks for the post this definitely makes sense. Could you also write about time complexity of deletion. Is my assumption correct for deletion?

[Niklas B.]

@Rajeshwar Yes I had that in an initial version but removed it for some reason while editing. The exact same reasoning that works for insertion applies for deletion as well. Check out whether the update answers your question

[David Rodríguez - dribeas]

Insertion at end in amortized O(1) depends on the growth strategy.

[Niklas B.]

@DavidRodríguez-dribeas That's trivially true. I should have said "there exists a strategy that allows for O(n-k) amortized insertion + deletion" But then that is true for every algorithm and I usually implicitely assume the "unless somebody decides to use a non-optimal approach to do it" appendix