Why is inserting at the end of a dynamic array O(1) while inserting in the middle is O(n)?

Question

Accordingly to the Wikipedia article on dynamic arrays, inserting/deleting at the end of the array is O(1) while inserting/deleting from the middle is O(n). Why exactly is that?

Also - if I have a dynamic array with 5 elements and I insert a new element at position 6 the operation is O(n) whereas if I use the function to append to the end of the array it is O(1). Isn't this the same operation assuming the array doesn't need to resize in either case? Or does appending to the dynamic array really insert the new element somewhere besides position 6?

Thanks!

EDIT: I think my main confusion is the difference between inserting at the end of the array and inserting at a specific position that is equivalent to the end of the array.

I suppose a pointer to the memory address of the end of the array is kept handy and that is why the append operation is quick. Conversely, if I specify a precise position (even if it is the end of the array) it won't know that inserting at that position is tantamount to using the aforementioned memory address so it has to traverse the entire array, eh?

Answer 1

To insert at the end of an array, you simply have to put the item there.

To insert into the middle of an array, you need to move the items after that point up by one.

To delete from the end of an array, you just drop its count by one.

To delete from the middle you have to do that and shift the other items down.

It's the shifting that turns it into O(n).

Answer 2

It's pretty simple:

Inserting in the middle involves moving each later element over by 1. To insert at the end, if there is additional space reserved, the item is just stored there, but if not new space is allocated. Thus this operation is done in amortized constant time.

Answer 3

The order of magnitude would depend entirely on what sort of data structure the "dynamic array" actually is ("dynamic array" isn't a strictly defined data structure, it's more of a desired result achieved by employing a particular data structure). The example that you give would be that reflect by a dynamic array achieved by employing a linked list. Adding to the end could be O(1) if the list structure kept a pointer to the final element. Inserting (regardless of the index) would require traversing the linked list, meaning one operation per node up until the desired index.

Answer 4

Actually, it's not Big-O but Big-Theta.

Answer 5

Adding to Adam Robinson's excellent summary: This isn't just theory. I've seen any number of situations in which a dynamic array was constructed by repeatedly appending to the end of the array. This works out to o(N**2) performance, because the array repeatedly needs to be re-allocated, forcing each of its members to be copied into the new array structure. The re-allocations may happen on only 1/10 of the append operations, but that's bad enough, and is still o(N**2) performance-wise.

In STL, this performance penalty can be avoided by calling vector::reserve(N) before writing into the vector; but that step is often overlooked.