Ringkasan kompleksitas semua struktur data — gunakan sebagai referensi cepat!

Analisis kompleksitas mengukur efisiensi kode dari segi waktu (time) dan ruang (space).

Time Complexity — Big O Cheat Sheet

Struktur Data:

*= average case

Space Complexity

// O(1) space — hanya variabel konstan
function sum(arr) {
  let total = 0;
  for (const n of arr) total += n;
  return total;
}

// O(n) space — array baru sebesar input
function double(arr) {
  return arr.map(n => n * 2);
}

// O(n) space — rekursi depth n
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // n call stack frames
}

Tips Optimasi

1. Gunakan Hash Map untuk mengubah O(n²) jadi O(n):

// O(n²) — nested loop
function twoSumSlow(arr, target) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] + arr[j] === target) return [i, j];
}

// O(n) — hash map
function twoSumFast(arr, target) {
  const seen = new Map();
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(arr[i], i);
  }
}

2. Trade-off — sering bisa tukar waktu dengan ruang (dan sebaliknya):
   • Caching/memoization: lebih cepat tapi butuh memori
   • In-place algorithm: hemat memori tapi bisa lebih lambat

🎭 Analogi sehari-hari: Cheat sheet ini = peta wilayah saat kamu coding interview. Hafalin? Tidak harus. Tapi kalau lihat sekilas 5 detik dan langsung tau "oh masalah ini Hash Map cocok" = kamu lebih dari 50% jalan ke solusi.

💡 Pola umum optimasi: tukar ruang dengan waktu.

• Brute force: lambat tapi hemat memori
• Cache/memo/Hash Map: tambah memori untuk hilangkan loop berulang
• Pre-compute: hitung sekali di awal, query berkali-kali jadi instan

Hampir semua optimasi algoritma = trick "saya bayar memori sedikit, dapat speedup besar".

⚠️ Jebakan baca tabel kompleksitas:

• Hash Map O(1) bintang — itu average case, worst case O(n) kalau hash buruk
• BST O(log n) bintang — itu kalau balanced. Unbalanced = O(n)
• Lupa space complexity — algoritma cepat tapi bocorin RAM = bikin server crash
• Konstanta kebablasan — algoritma O(n) dengan konstanta 100 bisa lebih lambat dari O(n log n) konstanta 1 untuk n kecil

🎯 Tips interview "kompleksitas":

1. Bilang dulu brute force + Big O-nya (selalu ada solusi naif)
2. Tunjuk bottleneck ("ini O(n²) karena nested loop")
3. Usulkan optimasi ("Hash Map bisa hilangkan inner loop → O(n)")
4. Sebut trade-off ("trade O(n) extra space")
5. Jangan lupa space complexity kecuali ditanya hanya time

🧪 Tebakan cepat: Two Sum, sorted array. Brute force O(n²). Pakai 2 pointer (left & right) → O(n) time, O(1) space. Pakai hash map → O(n) time, O(n) space. Sorted = pilih 2-pointer (lebih hemat memori).

TL;DR: Kompleksitas = bahasa untuk negosiasi performa. Time + space + amortized + worst-case semua perlu disebut. Trade-off ruang ↔ waktu adalah trick utama optimasi.