Big-O & Analisis Kompleksitas

Kenapa ini penting

Hampir setiap interviewer akan bertanya, setelah kamu menulis solusi: "What's the time and space complexity of this?" Kalau kamu menjawab "eh... cepat kok", itu sinyal merah. Big-O adalah bahasa bersama engineer untuk membicarakan seberapa cepat kebutuhan waktu dan memori tumbuh ketika input membesar. Tanpa bahasa ini, kamu tidak bisa membandingkan dua solusi, tidak bisa menjelaskan kenapa solusi kedua lebih baik, dan tidak bisa tahu kapan harus berhenti mengoptimasi.

Analogi: kamu mencari nama teman di buku telepon. Cara pertama, baca dari halaman pertama sampai ketemu; kalau bukunya dua kali lebih tebal, waktumu dua kali lebih lama. Cara kedua, buka di tengah, lihat apakah namanya sebelum atau sesudah, buang separuh, ulangi; bukunya dua kali lebih tebal, kamu hanya butuh satu langkah tambahan. Cara pertama O(n), cara kedua O(log n). Untuk buku 1 juta nama, bedanya kira-kira 1.000.000 langkah lawan 20 langkah.

Konsep inti

Apa yang diukur

Big-O menggambarkan batas atas pertumbuhan jumlah operasi terhadap ukuran input n, dengan dua aturan penyederhanaan:

1. Buang konstanta: O(2n) ditulis O(n). Kita peduli bentuk kurvanya, bukan angkanya.
2. Ambil suku dominan: O(n² + n) ditulis O(n²), karena saat n besar, n² mengalahkan segalanya.

Time complexity mengukur jumlah langkah. Space complexity mengukur memori tambahan yang kamu alokasikan (biasanya input tidak dihitung, tapi sebutkan asumsi ini saat interview). Rekursi juga memakai memori lewat call stack: rekursi sedalam n = O(n) ruang.

Kelas yang paling sering muncul

Patokan kasar yang sering dipakai saat latihan (pola umum dari komunitas competitive programming, bukan hukum): kalau batas input sekitar 10⁵ sampai 10⁶, targetkan O(n) atau O(n log n); kalau sekitar 10³, O(n²) biasanya masih aman; kalau sekitar 20, O(2ⁿ) mungkin diterima. Tanyakan batas input ke interviewer, karena itu petunjuk solusi yang diharapkan.

Biaya tersembunyi di JavaScript

Banyak method bawaan terlihat seperti satu langkah padahal loop di dalamnya:

Cara menjelaskan saat interview

Jangan hanya menyebut hurufnya. Jelaskan dari mana angkanya:

"The outer loop runs n times, and for each iteration I do a constant-time hash map lookup, so the total time is O(n). I store at most n entries in the map, so space is O(n)."

Kalau ada dua input berbeda, pakai dua variabel: "This is O(n + m), where n is the length of the first array and m the second." Jangan paksa jadi O(n).

Contoh kode

Kode ini menghitung jumlah langkah sungguhan untuk beberapa kelas kompleksitas, supaya perbedaannya terasa.

// Menghitung "langkah" agar Big-O terlihat nyata, bukan cuma teori
function constant(arr) { let ops = 0; ops++; return { val: arr[0], ops }; }        // O(1)
function linear(arr) { let ops = 0; let max = -Infinity;
  for (const x of arr) { ops++; if (x > max) max = x; } return { val: max, ops }; } // O(n)
function quadratic(arr) { let ops = 0; let pairs = 0;
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++) { ops++; if (arr[i] + arr[j] === 0) pairs++; }
  return { val: pairs, ops }; }                                                     // O(n^2)
function logarithmic(n) { let ops = 0; while (n > 1) { n = Math.floor(n / 2); ops++; } return { ops }; } // O(log n)

for (const n of [10, 100, 1000]) {
  const arr = Array.from({ length: n }, (_, i) => i - n / 2);
  console.log(`n=${n}`, 'O(1):', constant(arr).ops, '| O(log n):', logarithmic(n).ops,
    '| O(n):', linear(arr).ops, '| O(n^2):', quadratic(arr).ops);
}
// → n=10 O(1): 1 | O(log n): 3 | O(n): 10 | O(n^2): 45
// → n=100 O(1): 1 | O(log n): 6 | O(n): 100 | O(n^2): 4950
// → n=1000 O(1): 1 | O(log n): 9 | O(n): 1000 | O(n^2): 499500

// Ruang (space): dua cara membalik array
function reverseCopy(arr) { const out = []; for (let i = arr.length - 1; i >= 0; i--) out.push(arr[i]); return out; } // O(n) ruang
function reverseInPlace(arr) { let l = 0, r = arr.length - 1;
  while (l < r) { [arr[l], arr[r]] = [arr[r], arr[l]]; l++; r--; } return arr; }   // O(1) ruang tambahan
console.log(reverseCopy([1, 2, 3, 4]), reverseInPlace([1, 2, 3, 4]));
// → [ 4, 3, 2, 1 ] [ 4, 3, 2, 1 ]

// Jebakan: includes di dalam filter = O(n*m), bukan O(n)
function commonSlow(a, b) { return a.filter(x => b.includes(x)); }
function commonFast(a, b) { const set = new Set(b); return a.filter(x => set.has(x)); } // O(n + m)
console.log(commonSlow([1, 2, 3, 4], [3, 4, 5]), commonFast([1, 2, 3, 4], [3, 4, 5]));
// → [ 3, 4 ] [ 3, 4 ]

Perhatikan: saat n naik 10 kali, O(n) naik 10 kali, O(n²) naik sekitar 100 kali, O(log n) hanya bertambah 3. Itulah kenapa mengubah O(n²) menjadi O(n) adalah "kemenangan" yang paling dicari interviewer.

Kesalahan umum

1. Menganggap method bawaan gratis. b.includes(x) di dalam loop membuat solusi O(n·m). Cara benar: ubah b menjadi Set dulu.
2. Lupa ruang call stack. Rekursi DFS di tree yang miring (seperti linked list) sedalam n memakai O(n) ruang. Sebutkan "O(h) where h is the height of the tree".
3. Menyamakan dua input menjadi satu n. Cara benar: O(n + m) atau O(n · m) sesuai faktanya.
4. Lupa biaya sort. Kalau kamu mengurutkan dulu, solusimu minimal O(n log n) walau sisanya O(n).
5. Menjawab Big-O tanpa alasan. Cara benar: tunjuk bagian kode yang menentukan kompleksitas (loop luar, lookup di dalam, dan ruang struktur data).

Latihan

1. Mudah, Fungsi sumAndProduct(arr) menjumlahkan semua elemen dengan satu loop, lalu mengalikan semua elemen dengan loop kedua (lihat kodenya di solusi). Apa time dan space complexity-nya?
2. Sedang, Tentukan kompleksitas: (a) loop i dari 0 sampai n, di dalamnya loop j dari 0 sampai 10; (b) while (n > 1) n = n / 3; (c) loop atas n yang di dalamnya memanggil arr.shift().
3. Menantang, Tulis tiga versi hasDuplicate(arr): O(n²) waktu O(1) ruang, O(n log n), dan O(n) waktu. Jelaskan trade-off masing-masing.

function sumAndProduct(arr) { let s = 0; for (const x of arr) s += x; let p = 1; for (const x of arr) p *= x; return [s, p]; }
console.log(sumAndProduct([1, 2, 3, 4])); // → [ 10, 24 ]

const dupBrute = a => { for (let i = 0; i < a.length; i++) for (let j = i + 1; j < a.length; j++) if (a[i] === a[j]) return true; return false; };
const dupSort = a => { const s = [...a].sort((x, y) => x - y); for (let i = 1; i < s.length; i++) if (s[i] === s[i - 1]) return true; return false; };
const dupSet = a => new Set(a).size !== a.length;
for (const t of [[1, 2, 3], [1, 2, 1], []]) console.log(JSON.stringify(t), dupBrute(t), dupSort(t), dupSet(t));
// → [1,2,3] false false false
// → [1,2,1] true true true
// → [] false false false

Ringkasan

• Big-O mengukur pertumbuhan waktu/ruang terhadap ukuran input; buang konstanta dan ambil suku dominan.
• Urutan dari tercepat: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
• Method bawaan seperti includes, shift, slice, dan sort punya biaya tersembunyi.
• Space complexity mencakup struktur data tambahan dan kedalaman call stack rekursi.
• Saat interview, jelaskan asal angka Big-O dari struktur kodenya, pakai variabel terpisah untuk input berbeda.