Kamu sering dengar kalimat seperti "JavaScript Array.push itu O(1) amortized". Apa sih maksudnya?

Amortized analysis adalah cara mengukur kompleksitas rata-rata per operasi dalam jangka panjang, bukan dalam satu operasi tunggal. Beberapa operasi boleh lambat (O(n)), asal cukup jarang sehingga rata-ratanya tetap cepat.

Motivasi: kenapa "worst case" saja tidak cukup

Worst case melihat operasi terburuk yang mungkin terjadi sekali. Tapi dalam praktik, yang kita peduli adalah total biaya untuk N operasi. Kalau dari N operasi cuma 1 yang lambat dan 999 cepat, rata-rata per operasi tetap cepat — dan itu yang dilihat pengguna.

Analogi: bayar parkir Rp 3.000/hari setiap hari = sama mahalnya dengan bayar Rp 90.000 sekaligus sekali sebulan. Biaya totalnya identik; hanya distribusinya berbeda.

Contoh klasik: dynamic array resize

JavaScript Array (dan Python list, Java ArrayList, Go slice) adalah dynamic array — ukurannya bertambah otomatis. Tapi memori fisik array harus berurutan, jadi saat kapasitas penuh, implementasi melakukan:

1. Alokasi array baru, biasanya 2× ukuran lama
2. Copy semua elemen lama ke array baru
3. Tambahkan elemen baru
4. Buang array lama

Langkah 2 itu O(n). Jadi sekilas, push kadang O(1) (ada ruang) dan kadang O(n) (harus resize).

Apakah pushnya "benar-benar" O(n)? Tidak — karena resize sangat jarang.

Hitung dengan aggregate method: untuk n operasi push mulai dari array kosong, berapa total operasi?

Total biaya untuk n push ≈ n + (1 + 2 + 4 + 8 + ... + n) ≤ n + 2n = 3n. Rata-rata per push = 3n / n = O(1) amortized.

Artinya: "push boleh sesekali O(n), tapi frekuensinya menurun eksponensial, jadi rata-ratanya tetap konstan."

const arr = [];
// 1 juta push
for (let i = 0; i < 1_000_000; i++) {
  arr.push(i); // total ~3 juta operasi dasar, bukan n²
}

Contoh kedua: hash table rehash

Hash table juga resize saat load factor (size / capacity) melewati threshold (biasanya 0.75). Saat rehash, setiap key dihitung ulang hashnya dan dipindah ke bucket baru — itu O(n).

Tapi seperti dynamic array, rehash terjadi setiap ~2× pertumbuhan, sehingga amortized cost set / get / delete tetap O(1).

Banker's method: intuisi "simpan tabungan"

Cara lain memandangnya: setiap operasi "cepat" membayar biaya ekstra (misalnya 3 unit, bukan 1) — kelebihannya disimpan sebagai tabungan di setiap elemen.

Saat resize datang, tabungan itu dipakai untuk membayar copy. Karena tiap elemen sudah menabung cukup sebelum resize, biaya resize sudah lunas dari sisi akunting — jadi tidak membebani operasi apapun saat itu.

Ini hanya trik pembuktian — intuisinya: biaya mahal sudah "di-prepay" oleh banyak operasi murah sebelumnya.

Amortized vs Average case — jangan tertukar

Amortized lebih kuat dari average case — dia berlaku untuk sekuens operasi apapun, bahkan adversarial. Tapi dia berlaku pada sekuens, bukan pada satu operasi. Jadi kalau kamu peduli latency per operasi (misalnya real-time systems), amortized tidak cukup — kamu mungkin butuh struktur dengan worst case yang terjamin (misalnya balanced BST dibanding hash table).

Intinya

• Beberapa struktur punya operasi yang "kadang mahal", tapi frekuensinya diatur supaya total biayanya tetap rendah.
• push di dynamic array, set di hash map, union di union-find — semuanya amortized O(1).
• Saat kamu baca "amortized O(1)" di dokumentasi, artinya: aman untuk dipakai dalam loop, tapi ada satu operasi sesekali yang jauh lebih lambat — waspada kalau aplikasimu sensitif terhadap jitter latency.

🎭 Analogi sehari-hari: Bayar parkir pakai kartu pulsa.

• Sekali isi ulang Rp 50.000 = lambat (antri di counter, copot kartu, isi, balik)
• 100 transaksi parkir berikutnya = cepet, tinggal tap
• Rata-rata: cepet (amortized fast). Walau ada 1 transaksi yang lambat di antaranya.

Itulah dynamic array push: 99% cepat, 1% resize lambat, rata-ratanya tetap O(1).

💡 Mengapa 2× resize, bukan +10 tiap kali? Resize +konstan = O(n²) total cost. Resize ×2 = total cost = sum of geometric series ≤ 2n = O(n) total = O(1) per push amortized. Inilah kenapa hampir semua dynamic array (Vector di C++, ArrayList di Java, list di Python, slice di Go) pake growth factor multiplier, bukan additive.

⚠️ Jebakan umum:

• Real-time / latency-sensitive systems = amortized O(1) gak cukup. 1 push lambat bisa miss frame deadline. Pakai struktur dengan worst-case terjamin
• Lupa amortized ≠ guaranteed — interview boleh tulis "O(1)*", jangan ditelan tanpa caveat
• Pre-allocate kalau tau ukuran = new Array(n) di JS atau make([]int, 0, n) di Go = hindari resize sama sekali

🎯 Worst-case vs Amortized vs Average:

• Worst-case = paling pesimis untuk 1 operasi (real-time, safety critical)
• Amortized = rata-rata atas sekuens operasi (typical web/server)
• Average = rata-rata atas distribusi input acak (analisis algoritma probabilistik)

🧪 Tebakan cepat: arr.push(x) 1jt kali. Total operasi? Worst-case naive: O(n²) = 1 triliun. Amortized real: ~3jt = O(n) total = O(1) per push. Beda: 1 juta kali lipat.

TL;DR: Amortized = rata-rata per operasi atas urutan operasi. Resize sesekali OK karena dibagi banyak operasi cepat. Aman untuk loop, tapi awas latency real-time.