Dlaczego dopisanie do dynamicznej tablicy jest amortyzowane O(1)?

Odpowiedź

Większość dopisań trafia w wolne miejsce i kosztuje O(1). Czasem następuje powiększenie i kopiowanie O(n) elementów; rozłożone na wiele dopisań daje średnio O(1) na operację (amortyzacja).

let capacity = 4;
let size = 0;

function append(x: number) {
  if (size === capacity) {
    capacity *= 2; // resize + copy O(n)
  }
  size++;
}