Time complexity of unshift() vs. push() in Javascript
I know what is the difference between unshift()
and push()
methods in JavaScript, but I'm wondering what is the difference in time complexity?
I suppose for push()
method is O(1) because you're just adding an item to the end of array, but I'm not sure for unshift()
method, because, I suppose you must "move" all the other existing elements forward and I suppose that is O(log n) or O(n)?
push() is faster.
js>function foo() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.unshift(1); return((new Date)-start)}
js>foo()
2190
js>function bar() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.push(1); return((new Date)-start)}
js>bar()
10
function foo() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.unshift(1); return((new Date)-start)}
console.log(foo())
function bar() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.push(1); return((new Date)-start)}
console.log(bar());
Update
The above does not take into consideration the order of the arrays. If you want to compare them properly, you must reverse the pushed array. However, push then reverse is still faster by ~10ms
for me on chrome with this snippet:
var a=[];
var start = new Date;
for (var i=0;i<100000;i++) {
a.unshift(1);
}
var end = (new Date)-start;
console.log(`Unshift time: ${end}`);
var a=[];
var start = new Date;
for (var i=0;i<100000;i++) {
a.push(1);
}
a.reverse();
var end = (new Date)-start;
console.log(`Push and reverse time: ${end}`);
The JavaScript language spec does not mandate the time complexity of these functions, as far as I know.
It is certainly possible to implement an array-like data structure (O(1) random access) with O(1) push
and unshift
operations. The C++ std::deque
is an example. A Javascript implementation that used C++ deques to represent Javascript arrays internally would therefore have O(1) push
and unshift
operations.
But if you need to guarantee such time bounds, you will have to roll your own, like this:
http://code.stephenmorley.org/javascript/queues/