Big O and Complexity
Amortised Analysis
Written by Swapnil RajaPublished
Some operations are usually instant and occasionally expensive. Amortised analysis is how you describe that honestly instead of quoting either extreme.
The problem it solves
A dynamic array has a fixed capacity. When you push past it, the engine allocates a bigger block and copies everything across - an O(n) operation. So how is push described as O(1)?
Because the expensive step is rare, and it gets rarer as the array grows. Capacity doubles each time, so the copies happen at sizes 1, 2, 4, 8, 16 and so on. Across n pushes the total copying work is about 2n, which averages to a constant per push.
Where the cost actually lands
javascript
// A dynamic array, written out so the copying is visible.
class Growable {
constructor() {
this.data = new Array(1)
this.length = 0
this.copies = 0
}
push(value) {
if (this.length === this.data.length) {
const bigger = new Array(this.data.length * 2)
for (let i = 0; i < this.length; i++) bigger[i] = this.data[i]
this.copies += this.length // the expensive step
this.data = bigger
}
this.data[this.length++] = value
}
}
const list = new Growable()
for (let i = 0; i < 1000; i++) list.push(i)
console.log(list.copies) // 1023
console.log(list.copies / list.length) // ~1.02 per push