Worst-case time for adding 1 element to expanding array

Question

Suppose we have an expanding array that doubles in size when we try to add something to it but it is filled.

According to the bottom of the slide "Amortization: Expanding Vectors" the worst-case time for adding one element is 2N, not N? Why is this?

I thought it would be N because copying N elements to the new, double sized array, would take N time.

For example, say I'm adding just one element to a filled array of size 4. It would go like this:

Make new array of size 8 (double of 4).
Copy all of elements of original array to new array (copy 4 times).
Set 5th element of the new array to the additional element (copy 1 time).

So that would copy elements 5 times, which is N + 1, not 2N?

That PDF seems to nicely explain how it's derived, can you tell us what you're not understanding so the answers can better address the question? — nanofarad
– nanofarad, Commented Oct 14, 2013 at 21:00
Also remember that for the purpose of asymptotic analysis, O(2N) = O(N) — Mike Dinescu
– Mike Dinescu, Commented Oct 14, 2013 at 21:02
I'm not confused about the amortized insertion time, which is 2 units, making the time of adding N elements 2N. I'm confused about adding just one element: Why is it 2N? — George Newton
– George Newton, Commented Oct 14, 2013 at 21:08

Lukas Eichler · Accepted Answer · 2013-10-14 21:23:33Z

1

The operations needed for adding an element to an exanding array is O(2N) because first you need to go through the whole array and check for empty space with O(N). Because this is the worst case there isn't any and you have to create a new array and copy the whole content from the first to the new array with O(N). Both operations combined result in O(2N).

When you think of array length the length is actually the size that is reserved for the array and not the number of elements inside. That is why you need to loop through the whole array for an empty space if you did not save the number of elements anywhere. I am speaking of 'empty space' because it is not stated that just elements were added and none were deleted inside the array.

answered Oct 14, 2013 at 21:23

Lukas Eichler

5,9331 gold badge27 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Worst-case time for adding 1 element to expanding array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related