Calculating Time Complexity of a Dynamic Array

Question

Calculating Time complexity of a Dynamic Based Array.

In the text i am reading it mentions two approaches for dynamically increasing an array.

Dynamic Array Approach 1

The first approach states that you can construct an array of size 1 and dynamically increase it for every time you push a new data to the array. For instance if you push new data then you create a new array of old size of the array plus 1 and copy all the elements from the old array to the new one and then add the new data. The text is suggesting that time complexity for this approach is 0(N^2). I am not sure how though? I thought the time complexity is O(N) since you are creating a new array for every new element where you can have N new elements and also you are copying the old elements which is again approximated to N. Therefore i would think that complexity is O(N).

Dynamic Array Approach 2

The second approach is suggesting that we can reduce time complexity by doubling the capacity of the array every time it is full. For instance if we have an array of initial capacity size 4 and we make it full then when attempting to add new data we would create a new array of size 8 and copy all the old elements to this new array and then add the new data.

The text further states that the time complexity for this approach is O(N).

Can someone please clarify how is the time complexity for the approach also O(N) ?

Answer 1

Imagine that one starts with an array with space for 1 item and that we proceed to append N items, 1 at a time. The first time we have to copy 1 item to the larger space, the second time 2 items and so on. Before adding the Nth item we need to copy the N-1 existing items, so overall we've done

1 + 2 + 3 + ... N-1 = N(N-1)/2

Copies, so this is O(N^2)

With the second approach we copy far less often: the first and second copies happen as we add those items, but then the next copy doesn't happen until a size 4 buffer is full and the one after that when a size 8 buffer is full.

If k is such that 2^(k-1) < N <= 2^k then we'd do

1 + 2 + 4 + 8 + ... 2^(k-1) = 2^k - 1 

Copies , i.e this is O(N)

Answer 2

If the array element storage location already exists in memory the time is only that of a memory write.

When it does not exist then more memory needs to be allocated to the array.

The increased time factor is the number of instruction cycles used in the routine to read the existing array, append the new element then write the array back to memory vs. just writing the new element to an existing memory location. The less often you have to do this using the reallocation method described.

The formula would be simple if every array element stored was the same size.