Big-O Notation untuk Pemula: Kenapa O(n) Lebih Baik dari O(n²)?

Kenapa Kita Perlu Mengukur "Kecepatan" Algoritma?

Bayangkan Anda diminta mencari nama "Budi" di dalam buku telepon setebal 1000 halaman. Ada dua cara:

1. Buka halaman pertama, baca satu per satu sampai ketemu (atau sampai halaman terakhir kalau tidak ada).
2. Buka halaman tengah, cek apakah "Budi" ada di sebelum atau sesudah situ (karena buku telepon terurut alfabetis), lalu ulangi di separuh bagian yang relevan.

Cara kedua jelas jauh lebih cepat untuk buku setebal 1000 halaman. Big-O Notation adalah cara formal untuk mendeskripsikan seberapa cepat (atau lambat) sebuah algoritma bertambah lambat seiring bertambahnya jumlah data—bukan mengukur waktu dalam detik, tapi mengukur pola pertumbuhannya.

O(1) — Constant Time

Waktu eksekusi tidak berubah berapa pun jumlah datanya.

function ambilElemenPertama(array) {
  return array[0] // Selalu 1 langkah, entah array-nya berisi 10 atau 10 juta item
}

O(n) — Linear Time

Waktu eksekusi bertambah sebanding lurus dengan jumlah data. Ini pola pencarian cara pertama di analogi buku telepon tadi.

function cariNama(daftarNama, target) {
  for (const nama of daftarNama) {   // Paling buruk, harus memeriksa SEMUA elemen
    if (nama === target) return true
  }
  return false
}

Kalau datanya 10 kali lebih banyak, waktu eksekusinya (paling buruk) juga kira-kira 10 kali lebih lama.

O(log n) — Logarithmic Time

Ini pola pencarian cara kedua tadi (binary search)—setiap langkah membuang setengah dari sisa data yang perlu diperiksa.

function binarySearch(sortedArray, target) {
  let low = 0
  let high = sortedArray.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    if (sortedArray[mid] === target) return true
    if (sortedArray[mid] < target) low = mid + 1
    else high = mid - 1
  }
  return false
}

Bedanya sangat signifikan di skala besar: untuk mencari di 1 juta data terurut, pencarian linear (O(n)) butuh sampai 1 juta langkah di kasus terburuk, sementara binary search (O(log n)) hanya butuh sekitar 20 langkah (karena 2^20 kira-kira 1 juta). Syaratnya: data harus sudah terurut terlebih dahulu.

O(n²) — Quadratic Time

Waktu eksekusi bertambah sebanding dengan kuadrat jumlah data—biasanya muncul dari loop di dalam loop yang memeriksa setiap pasangan elemen.

function adaDuplikat(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {   // Loop di dalam loop!
      if (i !== j && array[i] === array[j]) return true
    }
  }
  return false
}

Untuk 10 item, ini "cuma" 100 kali pemeriksaan. Tapi untuk 10.000 item, itu jadi 100 juta kali pemeriksaan—inilah kenapa kode dengan nested loop yang tidak disadari sering jadi penyebab aplikasi tiba-tiba lambat drastis begitu datanya bertambah banyak di produksi.

Tabel Perbandingan Pertumbuhan

Perbedaan antara O(n) dan O(n²) terlihat kecil untuk data sedikit, tapi menjadi perbedaan antara "instan" dan "tidak akan pernah selesai" begitu data bertambah banyak.

Kenapa Ini Penting untuk Junior Developer?

Anda tidak perlu menghitung Big-O secara matematis presisi setiap hari. Tapi kebiasaan bertanya "apakah ada nested loop yang tidak perlu di sini?" atau "apakah struktur data ini (array vs object/Map untuk lookup) memengaruhi kecepatan pencarian?" akan menyelamatkan Anda dari bug performa yang baru ketahuan setelah data produksi membesar—jauh lebih sulit diperbaiki saat itu dibanding dicegah sejak awal.

Kesimpulan

Big-O bukan sekadar teori akademis—ini bahasa umum yang dipakai untuk mendiskusikan trade-off performa algoritma tanpa harus mengukur waktu eksekusi secara literal. Semakin besar skala data yang Anda tangani, semakin penting memahami apakah kode Anda akan tetap cepat atau justru melambat drastis seiring pertumbuhan data.