Time complexity of unshift() vs. push() in Javascript

Question

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)?

Answer 1

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/