📚 Topik: Amortized Analysis — Kenapa append ke Dynamic Array Disebut O(1) Kategori: Algorithms · Level: 2 (intermediate–advanced)

🎯 Tujuan Belajar

Setelah sesi ini, keputusan berikut jadi lebih baik:

1. Bisa membedakan amortized O(1) vs worst-case O(n) vs average-case, dan tahu kapan perbedaan itu menggigit (latency SLA, real-time, sistem dengan tail-latency budget).
2. Tahu kapan wajib pre-alokasi (make([]T, 0, n), reserve(), new ArrayList<>(n)) dan kenapa "premature optimization" bukan alasan untuk tidak melakukannya kalau n sudah diketahui.
3. Bisa memilih growth factor dengan alasan eksplisit (memory waste vs copy work vs allocator behavior), bukan "default library aja".
4. Bisa mengevaluasi struktur data baru: apakah klaim O(1)-nya amortized, dan apakah amortized-nya bertahan di workload kamu (persistent/backtracking/real-time = bisa hilang).

🧠 Penjelasan Inti

Masalah yang diselesaikan

Array statis punya alokasi memori kontigu dengan indexing O(1) — cache-friendly, pointer-arithmetic murni. Tapi ukurannya tetap saat alokasi. Kalau butuh tumbuh, dua pilihan naif:

Dynamic array menang karena satu trik: saat penuh, jangan alokasi n+1, alokasi k·n dengan k > 1. Dengan begitu resize jadi jarang, dan biayanya "diangsur" ke operasi-operasi yang murah.

Amortized ≠ average-case

Ini distingsi yang paling sering salah:

• Average-case — rata-rata atas distribusi input (probabilistik, butuh asumsi).
• Amortized — rata-rata atas urutan operasi untuk satu worst-case sequence (deterministik, tanpa asumsi distribusi).

Amortized O(1) artinya: untuk setiap urutan n operasi, total biaya ≤ c·n. Bukan "biasanya cepat". Tidak ada asumsi probabilistik sama sekali. Ini lebih kuat dari average-case, lebih lemah dari worst-case per-operasi.

⚙️ Cara Kerja Internal

Bukti: aggregate method

Misal growth factor k = 2, kapasitas awal 1. Append ke-n dari array kosong:

Append 1:  cap 1  → copy 0
Append 2:  cap 2  → copy 1
Append 3:  cap 4  → copy 2
Append 4:  cap 4  → copy 0
Append 5:  cap 8  → copy 4
...
Append n:  cap n  → copy n/2

Total elemen yang di-copy sampai n append:

1 + 2 + 4 + ... + n/2  =  n − 1  <  n

Total biaya = n (tulis elemen baru) + <n (copy) = < 2n. Bagi n → ≤ 2 operasi per append. Konstan. ∎

Generalisasi growth factor

Kapasitas yang di-copy: 1 + k + k² + ... + k^m ≈ k^(m+1)/(k−1) ≈ k·n/(k−1).

Biaya amortized per append:

A(k) = 1 + k/(k−1)

Perhatikan: angka absolutnya bergantung apakah "copy" dihitung sebagai 1 unit atau sizeof(T) unit. Yang penting: konstan, tapi konstantanya naik saat k turun. Ini trade-off memori vs CPU yang eksplisit, bukan free lunch.

Accounting (banker's) method

Bayangkan tiap append "menabung" kredit. Append biasa biaya 1, tapi kita charge 3 (atau A(k)): 1 untuk kerja nyata, sisanya ditabung di elemen itu. Saat resize, biaya copy c dibayar dari tabungan c elemen yang sudah ada — tiap elemen punya saldo ≥ 2 (atau k/(k−1)−1). Tabungan tidak pernah negatif → prepaid, tidak ada hutang. Itu definisi amortized yang valid.

Potential method (paling rigorous, dipakai di paper)

Definisikan fungsi potensial Φ = "energi tersimpan" di struktur data:

Φ(h) = 2·num(h) − capacity(h)      // untuk k = 2

Amortized cost = actual + ΔΦ.

• Append tanpa resize: actual = 1. ΔΦ = +2. Amortized = 3.
• Append dengan resize (num = c, cap = c → cap = 2c, num = c+1): actual = 1 + c. Φ_before = 2c − c = c, Φ_after = 2(c+1) − 2c = 2. ΔΦ = 2 − c. Amortized = (c+1) + (2−c) = 3.

Konstan di kedua kasus. Φ ≥ 0 selalu (karena capacity ≥ num... perlu 2·num − cap ≥ 0 yang berlaku saat cap ≤ 2·num, benar untuk k=2). Syarat formal: Φ(h₀) = 0 dan Φ(hᵢ) ≥ 0 untuk semua i. Terpenuhi. ∎

🏗️ Diagram / Pseudocode

append(x):
    if size == capacity:
        new_cap = grow(capacity)          # k·capacity, dibatasi min threshold
        new_buf = alloc(new_cap)          # ← biaya O(new_cap), bisa page fault
        memcpy(new_buf, buf, size)        # ← biaya O(size), memory bandwidth bound
        free(buf)                         # ← kadang tertunda (GC / refcount)
        buf = new_buf
        capacity = new_cap
    buf[size] = x
    size += 1

Timeline biaya per-append (k=2, n=16):

cost
 16 |                    █
  8 |              █     ·
  4 |        █     ·     ·
  2 |    █   ·     ·     ·
  1 |█ █ · █ · █ · █ · █ · █ · █ · █
    +─────────────────────────────────→ append #
      spike di 1,2,3,5,9,17  —  sisanya flat

Pola spike lalu datar inilah yang bikin amortized O(1) tapi worst-case per-op tetap O(n). Kalau kamu punya SLA p99, kamu hidup di spike itu.

Implementasi nyata (terverifikasi, baca langsung dari source)

Go — runtime/slice.go, fungsi growslice:

const threshold = 256
if oldCap < threshold {
    return doublecap          // 2x untuk slice kecil
}
for {
    // Transition from growing 2x for small slices
    // to growing 1.25x for large slices
    newcap += (newcap + 3*threshold) / 4
    if newcap >= newLen { break }
}

Threshold 256, bukan 1024. Formula halus ini masuk sejak Go 1.18 (sebelumnya: 2x di bawah 1024, 1.25x di atas). Sumber: go.dev/src/runtime/slice.go (dicek 2026). Konsekuensi: slice besar di Go punya amortized cost mendekati 5–6 unit per append — lebih mahal dari Java/C++ 2x, ditukar dengan waste memori lebih kecil.

Java — ArrayList.grow() (JDK 7+):

int newCapacity = oldCapacity + (oldCapacity >> 1);   // 1.5x

Amortized ~3 unit/append, waste maks 50%.

C++ — std::vector: standar tidak menspesifikasikan growth factor, hanya menjamin push_back amortized O(1). libstdc++ (GCC/Clang) pakai 2x; MSVC pakai 1.5x. Ini implementation detail — jangan diandalkan portabel.

Python — list pakai ~1.125x (newsize + newsize >> 3 + (newsize < 9 ? 3 : 6)), agresif hemat memori karena tiap elemen adalah pointer 8 byte ke objek heap.

⚖️ Trade-off & Kapan JANGAN Dipakai

Ini bagian inti.

1. Amortized O(1) adalah kebohongan di sistem latency-sensitive

Kalau kamu punya p99 latency budget 10ms dan satu request bisa memicu resize 10 juta elemen (copy ~80MB di []int64), itu 80MB memcpy ≈ 5–15ms di satu request. Amortized-nya tetap O(1). p99-mu tetap hancur. Amortized analysis merata-ratakan latency spike ke request lain yang tidak mengalaminya — secara matematis benar, secara operasional menyesatkan.

Kapan ini fatal: game loop (frame budget 16ms), audio processing, real-time control, HFT, database dengan latency SLO. Di domain itu, pre-allocate atau pakai struktur lain (ring buffer, chunked/deque).

2. Growth factor kecil (1.25x) = lebih banyak copy

Go memilih 1.25x untuk slice besar. Kalau workload kamu append 10 juta elemen, total copy ~50 juta elemen vs ~20 juta dengan 2x. Untuk tipe besar (struct 200 byte), itu 10GB vs 4GB memory bandwidth. Kalau n diketahui, growth factor jadi tidak relevan — langsung pre-alokasi.

3. Growth factor 2x dan interaksi dengan allocator

Argumen klasik (dari diskusi libstdc++ 2004, masih relevan sebagai reasoning, bukan hasil benchmark yang saya ukur): dengan 2x, blok baru selalu lebih besar dari total semua blok lama yang pernah dibebaskan (c + c/2 + c/4 + ... < 2c). Akibatnya allocator tidak bisa memakai ulang memori bebas — selalu mmap halaman baru → page fault + RSS naik. Dengan 1.5x, total blok bebas (3c) melebihi kebutuhan (1.5c), jadi realloc in-place mungkin.

Status: DIINFERENSI. Ini argumen analitis yang masuk akal dan menjelaskan kenapa MSVC pilih 1.5x, tapi besarnya efek sangat bergantung allocator (glibc malloc, jemalloc, tcmalloc beda perilaku). Jangan kutip sebagai angka benchmark.

4. Shrinking: sumber thrashing yang sering dilupakan

pop sampai size turun jauh tidak mengecilkan kapasitas di banyak implementasi (Java ArrayList tidak shrink otomatis). Kalau kamu shrink agresif tiap kali size < cap/2, pola append/pop bergantian di sekitar batas memicu resize bolak-balik tiap operasi → O(n) per op, amortized hancur.

Fix standar: shrink hanya saat size < cap/4 (hysteresis), supaya butuh cap/4 operasi append untuk memicu grow lagi. Buffer gap 4x mencegah osilasi.

5. Kapan JANGAN pakai dynamic array sama sekali

6. Pre-alokasi: kapan "premature optimization" bukan alasan

Kalau n diketahui dari input (misal len(rows) dari query DB), make([]T, 0, n) adalah koreksi kompleksitas, bukan micro-optimization. Bedanya: kamu mengubah O(n) copy tersembunyi jadi nol. Kalau n hanya estimasi longgar, over-allocate bisa lebih buruk (RSS naik, cache pressure) — estimasi 2x dari aktual masih masuk akal, 100x tidak.

🏭 Contoh Produksi & Failure Mode

1. Aliasing bug di Go — append mengembalikan slice baru, bukan memutasi

a := make([]int, 3, 10)     // len 3, cap 10
b := append(a, 99)          // TIDAK resize (cap cukup) → b.array == a.array
b[0] = 42
// a[0] == 42  ← kejutan. a dan b share backing array.

Kalau cap(a) == len(a), append akan alokasi baru dan a tidak terpengaruh. Perilaku berubah tergantung kapasitas — bug yang muncul hanya di beberapa code path, sulit direproduksi. Ini penyebab umum data corruption di parser/encoder yang mengembalikan sub-slice. Mitigasi: slices.Clone() sebelum append kalau ownership ambigu.

2. Latency spike dari realloc di jalur request

Pola umum: cache in-process berupa []Entry yang di-append terus tanpa bound. Setelah berjalan 6 jam, append ke-1.000.001 memicu copy 1M entry di tengah request handling → p99 naik 50ms sesekali, tidak terlihat di average. Fixed dengan pre-allocated fixed-size ring buffer + eviction.

3. Peak memory 2.5x saat resize (Java)

ArrayList grow dari cap c ke 1.5c: array lama masih hidup selama Arrays.copyOf berjalan. Peak = c + 1.5c = 2.5c. Di container dengan memory limit ketat, ini bisa OOM padahal data akhirnya cuma butuh 1.5c. Gejala: OOMKilled yang tidak konsisten, hanya saat resize besar. Mitigasi: pre-size dari awal, atau naikkan limit dengan margin 2.5x.

4. Go: append di dalam loop tanpa pre-alokasi pada slice besar

var out []Item
for _, r := range rows { out = append(out, convert(r)) }   // ~5 unit/element untuk slice besar

vs

out := make([]Item, 0, len(rows))                          // 1 unit/element

Untuk 1 juta Item 100 byte: beda ~400MB memory traffic. Terukur, bukan teori.

5. Amortized hilang saat persistence/backtracking

Struktur immutable (misal persistent vector) yang mengandalkan lazy evaluation + memoization: kalau kamu akses versi lama berulang kali, kerja yang tadinya "dibayar sekali" jadi dibayar ulang. Amortized bound tidak berlaku karena state global (cache/memo) di-share antar versi. Ini alasan paper Okasaki soal amortization in persistent data structures pakai teknik khusus (banker's queue dengan scheduling eksplisit), bukan amortized naif.

⚠️ Miskonsepsi Umum

1. "Append itu O(1)." Salah tanpa kualifikasi. Amortized O(1). Worst-case per operasi O(n). Kalau kamu menulis dokumentasi API atau SLO, tulis "amortized O(1), worst-case O(n)".

2. "Amortized O(1) berarti cepat." Tidak. Amortized cost konstantanya bisa 2, 3, atau 6 unit kerja. k=1.25 berarti ~5x lebih banyak memory traffic per append dibanding k=2. Konstanta itu nyata dan terukur.

3. "Amortized analysis berlaku di mana saja." Gugur untuk: (a) struktur persistent/immutable dengan state di-share, (b) struktur dengan operasi yang bisa di-interleave secara adversarial (attacker memicu resize tiap request = DoS amplification), (c) concurrent tanpa sinkronisasi — dua goroutine append bersamaan ke slice yang sama = data race, bukan soal kompleksitas.

4. "Growth factor 2x selalu lebih baik karena amortized cost-nya paling rendah." 2x punya amortized cost terendah (3 vs 4 vs 6) tapi waste memori tertinggi (100%). Kalau kamu simpan 10GB data, waste 100% = 20GB RSS. Itu bukan trade-off sepele. Tidak ada "best practice" universal — ini fungsi dari rasio memori-harga vs CPU-harga di deployment kamu.

5. "Karena amortized O(1), tidak perlu pre-alokasi." Pre-alokasi saat n diketahui menghilangkan semua resize dan semua copy — dari O(n) total jadi 0. Itu bukan optimasi mikro, itu menghilangkan pekerjaan.

6. "Resize = alokasi + copy." Sering ada komponen ketiga yang dilupakan: free/deallocation. Di runtime GC (Go, Java), array lama baru benar-benar dibebaskan setelah GC berikutnya — peak memory bisa lebih tinggi dari perkiraan, dan biaya GC proportional ke volume alokasi (yang naik karena resize).

✅ Cek Pemahaman

1. Sebuah dynamic array pakai growth factor k = 1.5, kapasitas awal 1, kamu append 3⁶ = 729 elemen. Hitung total elemen yang di-copy dan verifikasi amortized cost ≈ 3 unit/append. Lalu: berapa total copy kalau growth factor-nya 2.0? Bandingkan dan jelaskan implikasi untuk memilih k.

2. Kamu punya endpoint API dengan SLO p99 < 20ms. Di dalamnya ada loop yang meng-append ke slice yang tidak di-pre-alokasi, dan panjangnya bervariasi 0–5 juta elemen. Apakah "append itu O(1) amortized" cukup untuk membenarkan desain ini? Kalau tidak, sebutkan dua perbaikan konkret dan trade-off masing-masing.

3. Jelaskan kenapa potential function Φ = 2·num − capacity tidak valid kalau growth factor-nya 1.25 (hint: periksa syarat Φ ≥ 0 saat num mendekati capacity). Konstruksi Φ yang valid untuk k = 1.5 dan buktikan amortized cost-nya konstan.

🔑 Poin Kunci

• Dynamic array menukar O(n) copy yang jarang dengan O(1) amortized per append, lewat geometric growth (k > 1). Tanpa k > 1, jadi O(n²) total.
• Amortized cost per append ≈ k/(k−1): k=2 → 3, k=1.5 → 4, k=1.25 → 6. Konstanta naik saat k turun.
• Amortized ≠ average-case. Amortized berlaku untuk setiap urutan operasi, tanpa asumsi distribusi. Tapi worst-case per-op tetap O(n).
• Implementasi nyata berbeda: Go 2x→1.25x (threshold 256, formula halus sejak 1.18), Java 1.5x, libstdc++ 2x, MSVC 1.5x, CPython ~1.125x. C++ standar tidak menspesifikasikan factor.
• Pre-alokasi saat n diketahui bukan optimasi mikro — itu menghilangkan seluruh biaya copy.
• Resize punya peak memory > final size (Java: 2.5x) dan latency spike yang tidak terlihat di rata-rata. Amortized analysis menyembunyikan keduanya.
• Shrinking butuh hysteresis (shrink di cap/4, bukan cap/2) atau kamu dapat thrashing.
• Go append mengembalikan slice baru — aliasing behavior bergantung pada kapasitas. Sumber bug data corruption yang paling umum di kode Go.
• Amortized gugur untuk persistent/immutable structures, concurrent tanpa lock, dan workload adversarial.

➡️ Eksplorasi Lanjut

• Ordered by relevance ke arsitektur sistem: 1. Tail latency & coordinated omission — kenapa average latency menipu; baca Gil Tene "How NOT to Measure Latency". Ini pasangan alami dari "kenapa amortized menipu". 2. Chunked / unrolled data structures — Vec<Box<[T]>>, B-tree-backed vectors (Rust im crate), absl::InlinedVector. Trade-off: pointer stability + no giant copy, tapi traversal kurang cache-friendly. 3. Allocator behavior — jemalloc vs tcmalloc vs glibc malloc, dan kenapa growth factor berinteraksi dengan fragmentasi. Topik lanjutan: madvise(MADV_DONTNEED) dan RSS vs VSZ. 4. Amortized analysis untuk hash table — rehashing juga amortized O(1), tapi dengan twist: rehash bisa incremental (Redis dict, Java ConcurrentHashMap) untuk menghindari spike. Bandingkan dengan dynamic array. 5. Ring buffer & backpressure — struktur dengan worst-case O(1) append, dipakai di queue bounded (Disruptor, LMAX). Ini "jawaban" untuk kasus di mana amortized tidak cukup. 6. Splay tree — contoh amortized analysis yang lebih dalam (potential function non-trivial, O(log n) amortized per op tanpa worst-case guarantee). Latihan bagus untuk teknik potential method.

Catatan verifikasi: Klaim source code Go (threshold = 256, formula newcap += (newcap + 3*threshold)/4) dan Java (oldCapacity + (oldCapacity >> 1)) diverifikasi langsung dari source/diskusi implementasi, dicek 2026. Growth factor libstdc++/MSVC adalah implementation detail yang dilaporkan komunitas, bukan spesifikasi standar C++ — DIINFERENSI, jangan diandalkan portabel. Angka "amortized cost 3/4/6" adalah hasil derivasi matematis dari model biaya copy-per-elemen, bukan benchmark terukur; biaya riil bergantung sizeof(T), memory bandwidth, dan perilaku allocator.