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

Mofette

what do you mean by time complexity? execution time? – Linis

With a smart sparse array implementation, unshift could be close to constant-time, but I have to wonder if it'd be worth it to complicate normal array access. I personally don't think I've ever written a call to unshift. – Electrotechnics

@therao - He means the standard computer science definition in big-O terms. – Pianissimo

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/

Pianissimo

So what is the complexity in V8? – Bedspread

Answer 2

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}`);

Expert

the bigger the set, the bigger the difference, on my machine, macpro,using @Expert 's code above, with i<150000 unshift is more than 250 times slower; the jsperf examples referenced further up use arrays with only 4 elements. – Exceeding

@TheHe appears to be right though, my first test was run on Chrome (my comment above), then I ran the same test on the same machine on Safari, and push(...) was 10% faster. I did not expect such a big difference between javascript engines. Huh! ( just realised this q is 2 years old, and Safari has come a long way, I'm using Safari 7.1.6 on MacPro 2014 model.) – Exceeding

unshift/shift 94% slower than push/pop on Chrome 48 Win10. – Spiel

If anyone is curious, using push with shift is faster than unshift with pop. – Leannleanna

On safari 13.0 unshift takes 8ms and push takes 3ms – Weiner

Answer 3

For people curious about the v8 implementation here is the source. Because unshift takes an arbitrary number of arguments, the array will shift itself to accommodate all arguments.

UnshiftImpl ends up calling AddArguments with a start_position of AT_START which kicks it to this else statement

  // If the backing store has enough capacity and we add elements to the
  // start we have to shift the existing objects.
  Isolate* isolate = receiver->GetIsolate();
  Subclass::MoveElements(isolate, receiver, backing_store, add_size, 0,
                         length, 0, 0);

and takes it to the MoveElements.

  static void MoveElements(Isolate* isolate, Handle<JSArray> receiver,
                           Handle<FixedArrayBase> backing_store, int dst_index,
                           int src_index, int len, int hole_start,
                           int hole_end) {
    Heap* heap = isolate->heap();
    Handle<BackingStore> dst_elms = Handle<BackingStore>::cast(backing_store);
    if (len > JSArray::kMaxCopyElements && dst_index == 0 &&
        heap->CanMoveObjectStart(*dst_elms)) {
      // Update all the copies of this backing_store handle.
      *dst_elms.location() =
          BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index))
              ->ptr();
      receiver->set_elements(*dst_elms);
      // Adjust the hole offset as the array has been shrunk.
      hole_end -= src_index;
      DCHECK_LE(hole_start, backing_store->length());
      DCHECK_LE(hole_end, backing_store->length());
    } else if (len != 0) {
      WriteBarrierMode mode = GetWriteBarrierMode(KindTraits::Kind);
      dst_elms->MoveElements(heap, dst_index, src_index, len, mode);
    }
    if (hole_start != hole_end) {
      dst_elms->FillWithHoles(hole_start, hole_end);
    }
  }

I also want to call out that v8 has a concept of different element kinds depending what the array contains. This also can affect the performance.

It's hard to actually say what the performance is because truthfully it depends on what types of elements are passed, how many holes are in the array, etc. If I dig through this more, maybe I can give a definitive answer but in general I assume since unshift needs to allocate more space in the array, in general you can kinda assume it's O(N) (will scale linerally depending on the number of elements) but someone please correct me if I'm wrong.

Vinegarroon

Answer 4

Yes, you are right. The default Complexity of push() is O(1) and unshift() is O(n). Because unshift() has to increment all the elements that already present in the Array. But, push() has to insert an element at the end of the array, so none of the Array elements' index has to change. But, push() can also be said with Complexity of O(n) because of dynamic allocation of memory. In javascript, when you create a new Array without specifying the size you need, it will create an Array of the default value. Until the default size gets filled, the push operation takes O(1) Complexity. But, if the default size is full, the compiler has to create a new Contiguous block of memory which is twice the size of the default memory, and copy the already existing elements to the newly allocated memory. So, it takes O(n) time to move the elements from one Contiguous block of memory to another Contiguous block of memory.

If you know the number of elements that you are going to put in the array, you can avoid getting O(n) for inserting an element.

1. Initialize the Array with the required size, and fill it with a dummy value. let array = new Array(size).fill(0)
2. Iterate through the elements that you wanna push and change the values by its index.

for (let i = 0; i < size; i++) {
  array[i] = i
}

So, instead of push() we altered the index of the elements in their position. It's way more memory efficient and less complex than creating an array with a default value and pushing elements to it. As we are using up only the required amount of memory, no extra memory is wasted on it.

Georgiegeorgina

The statement about .push taking O(n) is wrong. It's amortized O(1) indeed. Please familiarize yourself with amortized algorithm complexity https://mcmap.net/q/21106/-what-is-constant-amortized-time – Overmantel

It's not true that JS array values have to take up contiguous memory locations. See https://mcmap.net/q/21107/-how-are-javascript-arrays-represented-in-physical-memory – Halle

Answer 5

One way of implementing Arrays with both fast unshift and push is to simply put your data into the middle of your C-level array. That's how perl does it, IIRC.

Another way to do it is have two separate C-level arrays, so that push appends to one of them, and unshift appends to the other. There's no real benefit to this approach over the previous one, that I know of.

Regardless of how it's implemented, a push or and unshift will take O(1) time when the internal C-level array has enough spare memory, otherwise, when reallocation must be done, at least O(N) time to copy the old data to the new block of memory.

Alodee

Answer 6

Short Answer

• Time Complexity for push: O(n)
• Time Complexity for unshift: O(m + n)

Where:

• m is the length of the existing array.
• n is the number of elements to be added.

• Time Complexity for pop: O(1)
• Time Complexity for shift: O(n), where n is the length of the array

Long Answer

Here's a Array Data Structure implementation in JavaScript, hope this will make things clear.

class XArray {
  constructor() {
    Object.defineProperties(this, {
      length: {
        writable: true,
        enumerable: false,
        configurable: false,
        value: 0,
      },
    });

    /** Configure the output of the Array object to return only values */
    const runtimeConsole = console;
    console = {
      ...console,
      log: function (data) {
        if (XArray.isArray(data)) {
          runtimeConsole.log(Object.values(data));
        } else runtimeConsole.log(data);
      },
    };
  }

  /**
   * Adds element(s) to the end of the array
   *
   * Time Complexity: O(n)
   * @param  {...any} elements
   */
  push(...elements) {
    for (const element of elements) {
      this[this.length] = element;
      this.length++;
    }
    return this.length;
  }

  pop() {
    const element = this[this.length - 1];
    delete this[this.length - 1];
    this.length--;
    return element;
  }

  /**
   * Adds elements to the beginning of the array
   *
   * Time Complexity: O(m + n)
   *
   * @param  {...any} elements
   */
  unshift(...elements) {
    for (let i = this.length - 1; i >= 0; i--) {
      this[i + elements.length] = this[i];
    }
    for (const index in elements) {
      this[index] = elements[index];
      this.length++;
    }
    return this.length;
  }

  shift() {
    const element = this[0];
    this.length--;

    for (let i = 0; i < this.length; i++) {
      this[i] = this[i + 1];
    }
    delete this[this.length];
    return element;
  }

  static isArray(array) {
    return array instanceof XArray;
  }
}

Phalanger

Answer 7

imho it depends on the javascript-engine... if it will use a linked list, unshift should be quite cheap...

Lethe

Perf on most websites would go through the floor if Array was implemented with a linked list... – Phototransistor

right. but for unshift operation with a linked list you get O(1) complexity. So it depends on the usecase. But most sites would rather optimize push over unshift. – Defamation

think no site at all would optimize (in changing underlying abstract datatype) the Array construct? so it totally depends on JS-VMs internal structure, optimizations und underlying datatypes. – Lethe

Answer 8

Unshift is slower than push because it also needs to unshift all the elements to the left once the first element is added. So for unshift time complexity is o(n) as opposed to o(1) for push

Conch

Answer 9

Unshift is O(n). If my array is ["cat", "dog"], and I unshift "moose" into first position, everything remaining in the array must "move." That is, each item, upon adding "moose" to the first position, has an increase in index.

Push is O(1). If my array is ["cat", "dog"] and I push "moose" onto the end of the array, everything can remain in place.

Memorialist