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?