Big O Notation mengukur seberapa cepat atau lambat suatu operasi seiring bertambahnya jumlah data.

Notasi yang paling umum (dari tercepat ke terlambat):

Cara membaca Big O:

// O(1) — Constant
function getFirst(arr) {
  return arr[0]; // Selalu 1 operasi, berapapun ukuran array
}

// O(n) — Linear
function findItem(arr, target) {
  for (let i = 0; i < arr.length; i++) { // Loop sebanyak n
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(n²) — Quadratic
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {     // n kali
    for (let j = i + 1; j < arr.length; j++) { // n kali
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

Perbedaan nyata saat n = 1.000.000:

• O(1): 1 operasi
• O(log n): 20 operasi
• O(n): 1.000.000 operasi
• O(n²): 1.000.000.000.000 operasi — sangat lambat!

Selalu pilih algoritma dengan Big O terkecil yang memungkinkan.

🎭 Analogi sehari-hari: Cari nama "Budi" di buku telpon.

• O(n) = baca dari halaman 1 sampai ketemu (linear search)
• O(log n) = buka tengah, "Budi" di sebelum atau sesudah? Buang setengahnya, ulangi (binary search)
• O(1) = buku telpon dengan tab huruf — langsung loncat ke "B" (hash map)

💡 Kenapa konstanta diabaikan? O(2n) ditulis O(n) — bukan karena konstanta gak penting, tapi saat n besar, perbedaan algoritma O(n) vs O(n²) jauh lebih besar daripada konstanta apapun. n=1jt: O(2n)=2jt, O(n²)=1 triliun. Konstanta kalah jauh.

⚠️ Jebakan umum:

• "Lebih cepat di laptop saya" — tes dengan data kecil. O(n²) yang terlihat oke di n=100 (10rb operasi) akan jebol di n=1jt (1 triliun operasi)
• Lupakan Big O space — algoritma cepat tapi ngabisin RAM = bikin server crash
• O(log n) di kode = pasti ada "membagi dua" (binary search, balanced tree). Kalau loop biasa, itu O(n)

🎯 Cara cepat tebak Big O:

1. Loop sekali atas n = O(n)
2. Loop bersarang atas n = O(n²)
3. Membagi data tiap iterasi = O(log n)
4. Rekursi memanggil 2x dengan n/2 = O(n log n)
5. Akses langsung tanpa loop = O(1)

🧪 Tebakan cepat: for (i=0; i<n; i++) for (j=0; j<i; j++) — Big O? Total operasi = 0+1+2+...+n-1 = n(n-1)/2 ≈ n²/2 = O(n²). Konstanta hilang.

TL;DR: Big O = pertumbuhan operasi seiring n bertambah, bukan waktu detik. Ukur skenario worst case. Konstanta diabaikan.