Code Quiz

Dynamic Array Amortized Growth Bug

Spot the resizing mistake that destroys the O(1) amortized push guarantee of a dynamic array.

Codejavascript
class DynamicArray {
  constructor() {
    this.data = new Array(1);
    this.length = 0;
    this.capacity = 1;
  }

  push(value) {
    if (this.length === this.capacity) {
      // grow the backing store
      this.capacity = this.capacity + 1;
      const next = new Array(this.capacity);
      for (let i = 0; i < this.length; i++) {
        next[i] = this.data[i];
      }
      this.data = next;
    }
    this.data[this.length] = value;
    this.length++;
  }

  get(i) {
    return this.data[i];
  }
}

The array works correctly but violates the expected performance contract. What is the bug?