Big O adalah cara menuliskan seberapa cepat jumlah langkah sebuah kode bertambah waktu datanya bertambah. Jumlah datanya disebut n, misalnya panjang sebuah array. Yang dihitung langkah, bukan detik, karena detik tergantung komputernya, sedangkan jumlah langkah sama di komputer mana pun.
🧪 Tebakan cepat: sebuah kode punya loop di dalam loop, dua-duanya jalan sepanjang array. Array-nya jadi 10 kali lebih panjang. Langkahnya jadi kira-kira berapa kali lipat: 10, 20, atau 100? Tebak dulu, jawabannya ada di bagian "Hitung langkahnya".
Hitung langkahnya
Ambil tiga pekerjaan pada array berisi n data:
getFirst(arr): ambil isi pertama.findItem(arr, target): cari satu nilai dengan mengecek isinya satu per satu.hasDuplicate(arr): cek ada isi kembar atau gak, dengan membandingkan tiap pasangan.
Ini jumlah langkah paling banyak (kasus terburuk: yang dicari gak ada, dan gak ada isi kembar):
| n | getFirst |
findItem |
hasDuplicate |
|---|---|---|---|
| 10 | 1 | 10 | 45 |
| 100 | 1 | 100 | 4.950 |
| 1.000 | 1 | 1.000 | 499.500 |
function getFirst(arr) {
return arr[0]; // 1 langkah, berapa pun panjang arr
}
function findItem(arr, target) {
for (let i = 0; i < arr.length; i++) { // paling banyak n putaran
if (arr[i] === target) return i;
}
return -1;
}
function hasDuplicate(arr) {
for (let i = 0; i < arr.length; i++) { // n putaran
for (let j = i + 1; j < arr.length; j++) { // tiap putaran, loop lagi
if (arr[i] === arr[j]) return true;
}
}
return false;
}
console.log(getFirst([4, 8, 15])); // 4
console.log(findItem([4, 8, 15], 15)); // 2
console.log(hasDuplicate([4, 8, 15])); // false
getFirstgak punya loop, jadi selalu 1 langkah. Ini O(1), dibaca "O satu", atau konstan.findItempunya satu loop. Datanya 10 kali lipat, langkahnya juga 10 kali lipat. Ini O(n), atau linear. Kadang yang dicari ketemu di awal, tapi Big O biasanya menghitung kasus terburuk.hasDuplicatepunya loop di dalam loop. Datanya 10 kali lipat, langkahnya kira-kira 100 kali lipat. Ini O(n²), dibaca "O n kuadrat". Itu jawaban tebakannya. Kalau diketik, n² biasa ditulisn^2, jadiO(n^2).
Kenapa 45, bukan 100? j mulai dari i + 1, jadi tiap pasangan cuma dibandingkan sekali, sekitar setengah dari n × n. Big O membuang pengali tetap seperti "setengah" itu, karena yang dilihat cuma bentuk pertumbuhannya. Loop di dalam loop yang dua-duanya jalan n kali penuh butuh tepat n × n langkah, dan itu juga O(n²).
Enam kelas yang sering ketemu
Dari yang paling hemat sampai yang paling boros, dengan jumlah langkah kira-kira untuk n = 1.000:
| Big O | Nama | Contoh | Langkah (n = 1.000) |
|---|---|---|---|
| O(1) | konstan | ambil arr[0] |
1 |
| O(log n) | logaritmik | binary search | sekitar 10 |
| O(n) | linear | satu loop | 1.000 |
| O(n log n) | linearitmik | sorting cepat, misalnya merge sort | sekitar 10.000 |
| O(n²) | kuadratik | loop di dalam loop | 1.000.000 |
| O(2ⁿ) | eksponensial | mencoba semua kombinasi pilih atau gak pilih | angka 302 digit |
log n artinya berapa kali n bisa dibagi dua sampai tinggal 1. Binary search mencari di data yang sudah urut dengan membuang setengah sisa data tiap langkah, mirip mencari kata di kamus: buka tengahnya, buang separuh yang salah, ulangi. 1.000 data butuh sekitar 10 langkah, dan 1.000.000 data cuma sekitar 20 langkah. Jadi untuk data besar, O(log n) jauh lebih cepat daripada O(n), O(n log n), apalagi O(n²).
Cara cepat menebak Big O
- Gak ada loop, langsung ambil: O(1). Membaca isi array lewat index, misalnya
arr[i], selalu O(1). - Satu loop atas semua data: O(n).
- Loop di dalam loop, dua-duanya atas semua data: O(n²), diketik
O(n^2). - Datanya dibagi dua tiap langkah: O(log n).
- Dua loop berurutan, bukan yang satu di dalam yang lain: n + n = 2n langkah, tetap O(n). Pengali tetapnya dibuang.
⚠️ Jebakan yang sering ketemu
- Tes cuma pakai data kecil. O(n²) di n = 100 baru 10.000 langkah, terasa instan. Di n = 1.000.000, jadi satu triliun langkah.
- Loop yang tersembunyi.
arr.includes(x)di dalam loop sebenarnya loop di dalam loop, karenaincludessendiri mengecek satu per satu. Hasilnya O(n²). - Big O bukan detik. Big O bicara soal pertumbuhan. Di data kecil, kode O(n²) yang sederhana bisa saja lebih cepat dari kode O(n) yang ribet. Big O memberi tahu siapa yang menang waktu datanya besar.
- Lupa memori. Big O juga dipakai untuk memori (space complexity). Kode yang cepat tapi menyalin data besar berkali-kali bisa kehabisan memori.
TL;DR: Big O menuliskan seberapa cepat jumlah langkah bertambah waktu jumlah data n bertambah, biasanya di kasus terburuk. Gak ada loop, misalnya arr[0]: O(1). Satu loop: O(n), datanya dua kali lipat, langkahnya dua kali lipat. Loop di dalam loop: O(n²), diketik O(n^2), datanya 10 kali lipat, langkahnya kira-kira 100 kali lipat. Membagi dua tiap langkah: O(log n), sekitar 20 langkah untuk sejuta data, jadi paling cepat untuk data besar di antara O(n²), O(n), dan O(n log n). Pengali tetap dibuang, jadi 2n tetap O(n).
