Time Complexity Analysis of Javascript Array unshift
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
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));
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).