2

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?

Rob Sobers
  • 20,737
  • 24
  • 82
  • 111
  • As to your edit, again it depends on the implementation. You could very well create a dynamic array that's smart enough to know that Insert(bound-1) is the same as Add. – Adam Robinson May 06 '09 at 02:47
  • Hmm...I realize I asked 2 relatively distinct questions in 1 post here. Adam Robinson gave a great answer to one and Pax gave a greater answer to the other. Any consensus on what should be the accepted answer??? – Rob Sobers May 06 '09 at 03:43
  • You're asking a biased group ;) Pick the one that gives a more helpful for applicable answer. – Adam Robinson May 06 '09 at 03:58
  • If we DELETE an element in the middle then we can just swap it with the last element in the array. This way we won't have to move all the succeeding elements one place to the left. We can always DELETE or INSERT in O(1) for an unsorted array. – limitlessriver May 15 '20 at 13:35

5 Answers5

10

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).

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
8

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.

Adam Robinson
  • 182,639
  • 35
  • 285
  • 343
  • This makes sense. Unfortunately on the platform I'm referring to in my example (UniData) I don't really know how the dynamic array is implemented under the covers...but from what you're saying I think it is a linked list. Dunno why they chose that over an array. – Rob Sobers May 06 '09 at 02:47
  • Many languages use a linked-list structure for their "dynamic arrays". Many also use actual native arrays that are declared with buffer arrays. Once the buffers fill up, they either chain a new array (creating a sort of array/linked-list hybrid) or allocate a brand new array with the proper new buffer size, then copy all of the existing data and destroy the old array. This can lead to quite a bit of memory fragmentation, though. – Adam Robinson May 06 '09 at 02:53
  • I have worked with UniData (UniBasic), "C" and Java systems since about 1993 ... most variables in UDT are just Strings, in the strict "C" sense (as UDT is built in "C"), which are arrays of bytes. So the term "dynamic array" applies as they are mutable. Adding to the beginning or end is generally faster because there are pointers to where that is. Adding to the middle involves multiple steps including multiple memory-allocations and data-shifting. Not efficient, just like Java String "+" (which is why StringBuilder was invented). Try using DIMensioned arrays or CALLC. – Darrell Teague Mar 27 '13 at 18:50
  • I can't think of any language which uses linked lists to implement dynamic arrays. Dynamic arrays indeed do not have a definite implementation, though they almost always mean that it's a dynamically sized array or a growable array. If someone calls a linked list a dynamic array I'd say that claim is wrong. They don't have the same time complexities and linked lists miss the CPU cache significantly more often. I would stop using a language entirely if it's primitive array type was a linked list, I cannot imagine having linear access times on an array. – tsturzl Jan 21 '20 at 15:50
1

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.

rlbond
  • 65,341
  • 56
  • 178
  • 228
0

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.

Dan Breslau
  • 11,472
  • 2
  • 35
  • 44
  • I suppose that's why it's typical to double the size of the array every time you re-allocate memory. – Rob Sobers May 06 '09 at 02:44
  • It's a typical practice for application writers. But don't *assume* that the class library will do this; many common ones grow by constant increments instead. 10 is the number I remember from MFC. – Dan Breslau May 06 '09 at 03:00
-2

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

Colin Burnett
  • 11,150
  • 6
  • 31
  • 40
  • No, it's Big-O. Inserting into a position could take constant time, if the position happens to located at the end. It is not bounded below by n. – Andrei Krotkov May 06 '09 at 02:33