Time Complexity Analysis of Javascript Array unshift

Hsin-Yu (Bryce) Huang
3 min readOct 14, 2020

--

There are so many discussions about the time complexity of Array.prototype.unshift() in Javascript, but there is no convincing conclusion.

Some people say unshift done its work in constant time (or O(1)), while others claim unshift takes linear time (or O(N)) to insert an element into an array.

I write this article for making things clear and giving a conclusive summary.

Disclaimer:
I’m not an expert in Javascript. I’m just a front-end engineer curious about Time Complexity of unshift, so if I am wrong please do not hesitate to correct me in the comment, thanks!
Also, my native language is not English, so there might be some incorrect uses of language. Feel free to let me know which word/sentence is unclear/misleading.

Array.prototype.unshift

Pseudocode and Theory

Screenshot from https://tc39.es/ecma262/#sec-array.prototype.unshift

The screenshot might seem intimidating, let me briefly explain it for you.

In the 4.c step, the program move elements already in the array back for argCount offset, where argCount is the number of items requested to insert into the head of the array. This step takes O(len) where len is the length of the array before inserting new items.

In the 4.f step, the program put elements in the items into the array one by one, from 0 to argCount - 1. This step takes O(argCount) .

Thus, in theory, the time complexity of unshift should be O(len + argCount), or O(n) where n is the length of the array.

Let’s test

To run the code, you can copy and paste the following code into the console of the Chrome inspector or try it in my codepen.

function test_unshift(itemNum) {
// Create an array with O(itemNum) elements
var arr= [];
for (var i = 0; i < itemNum; i++) arr.push(1);

// Test how long unshift takes
var start = performance.now();
arr.unshift(2)
var end = performance.now();
return end - start
}
// --------------------[1st try]--------------------
console.log(test_unshift(1e5));
// --------------------[2ed try]--------------------
console.log(test_unshift(1e6));
// --------------------[3rd try]--------------------
console.log(test_unshift(1e7));
Result of the testing script
Try it on codepen

Note: The output could be various from computer to computer.

The result shows that the unshift time grows as the items in the array grow 10 times and 100 times (from 1e5 to 1e6 to 1e7).

If the time complexity is O(1), the time unshift took to insert an item should remain constant regardless of the length of the array. So it’s not O(1).

Is the time complexity O(n)?
Observing the trend of the growth of running time from 1st try to 3rd try, the running time growth rate is approximately 10~20 times while the length of the array grows 10 times, though the “time system” on javascript is not reliable (it’s another story). In the test, the time complexity of Array.prototype.unshift is linear.

Conclusion

All in all, both theory and practical running tests reach the same conclusion: Time complexity of unshift is Linear or O(n).

--

--

Hsin-Yu (Bryce) Huang
Hsin-Yu (Bryce) Huang

Written by Hsin-Yu (Bryce) Huang

Software Engineer | Web Development | Information Security

Responses (1)