Dynamic Array pushing Vs Assigning to a Static Size Array: Time Complexity in JavaScript

user_8176451 0
Viewed 200

I have a dynamic array as shown below:

const array1 = [];

    for(let i = 0; i < 5; i++)
    array1.push(i+1);

and another array:

let Array2 = Array(6); //Note here the size is 6 as compared to the array1 which has initial size as 5.

for(let i = 0; i < 5; i++)
        Array2[i] = i+1;

Now I want to append an element to the last of the array as shown below:

array1.push(6);

Will the above operation will be O(n) as this process will result in array1 to be moved to a new array and then appending 6 at the end or will it just be O(1).

Also which declaration is better? const array1 = [] and then adding the elements to it, or initializing an empty array (whose size is known) and then substituting in the elements one by one.

So here's the example for the same:

It is known that first five elements are coming from a for loop (which invokes another function) and the last element is coming from a function getElement as shown below:

Method 1:

const Array1 = [];

for(let i = 0; i < 5; i++)
Array1.push(getFirstFiveElements(i));
//Where getFirstFiveElements is another function



Array1.push(gettheSixthElement());

or Method 2:

const Array2 = Array(6);
for(let i = 0; i < 5; i++)
Array2[i] = getFirstFiveElements(i);



Array2[Array2.length - 1] = gettheSixthElement();
javascript
2 Answers

It's always better to initialize an array whose size is known. Because when you push elements onto an array that lacks the number of empty slots needed, behind the scenes JavaScript has to copy the existing underlying array into a new array twice the size of the old array. Therefore adding values to the array is not O(1) on average because sometimes it results in the entire array being copied. Whereas if you initialize the array with a known size, all additions to the array are O(1).

user_105874130

Why do we need to initialize the length? Theoretically there is no need for this. It can even result in confusing behavior, because all tests that use the length to find out whether an array is empty or not will report that the array is not empty. Some tests show that setting the initial length of large arrays can be more efficient if the array is filled afterwards, but the performance gain (if any) seem to differ from browser to browser.

user_142722740
Related