← Back
Bahasa

Big-O Notation: Notes to Remember / Catatan untuk Diingat (AI Slop)

A practical, code-first guide to Big-O time and space complexity, in English and Indonesian.

## Apa yang diukur Bagaimana waktu atau memori bertambah seiring bertambahnya ukuran input (`n`). Notasi ini mengabaikan konstanta dan spesifikasi hardware — yang dilihat adalah **bentuk pertumbuhannya**, bukan detik pastinya.

Kelas-kelas umum (dari terbaik ke terburuk)

Notasi Nama Contoh
O(1) konstan akses index array, lookup map
O(log n) logaritmik binary search
O(n) linear satu loop
O(n log n) linearithmic sorting
O(n²) kuadratik nested loop, koleksi yang sama
O(2ⁿ) eksponensial rekursi naif, tanpa caching
O(n!) faktorial brute-force permutasi

Huruf hanyalah label untuk “ukuran sesuatu”

n, k, m semuanya bermakna sama: “seberapa besar hal yang sedang saya iterasi/proses di sini.” Jangan minder dengan huruf yang belum familiar — tanyakan variabel ini menghitung apa?

  • O(k log k) = mengurutkan satu item berukuran k (misalnya mengurutkan karakter dalam satu string)
  • O(n · k log k) = melakukan sort itu di dalam loop sebanyak n item

Notasi → bentuk kode (eksplisit, berdampingan)

O(1) — konstan

func first(items []int) int {
    return items[0]   // tidak ada loop, tidak bergantung pada len(items)
}

O(log n) — rentang mengecil separuh setiap langkah

for lo < hi {
    mid := (lo + hi) / 2
    if target < arr[mid] {
        hi = mid
    } else {
        lo = mid + 1
    }
}

Ciri: ruang pencarian mengecil separuh setiap iterasi — bukan pass penuh.

O(n) — satu loop atas n item

for _, x := range items {
    sum += x
}

Ciri: satu loop, melewati seluruh koleksi sekali.

O(n log n) — loop/sort di mana bagian “log” terjadi pada seluruh n

sort.Slice(items, func(i, j int) bool { return items[i] < items[j] })

Ciri: mengurutkan seluruh koleksi berukuran n sekali, atau loop atas n di mana tiap langkahnya melakukan operasi log n (misalnya binary search di dalam loop).

O(n²) — dua nested loop, koleksi SAMA

for i := range items {
    for j := range items {
        // bandingkan items[i], items[j]
    }
}

Ciri: kedua loop bergantung pada n yang sama.

O(n·m) — dua nested loop, DUA KOLEKSI BERBEDA

for i := range listA {      // ukuran n
    for j := range listB {  // ukuran m
        // bandingkan listA[i], listB[j]
    }
}

Ciri: dua ukuran yang independen — n dan m tidak harus berhubungan.

O(k log k) — sort terjadi DI DALAM satu item, bukan lintas koleksi

func sortString(s string) string {   // s memiliki panjang k
    b := []byte(s)
    sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
    return string(b)
}

Ciri: sort dilakukan pada substruktur (satu kata), bukan seluruh koleksi luar.

O(n · k log k) — hal di atas, dipanggil sekali per item dalam loop luar

for _, s := range strs {        // n string
    key := sortString(s)        // O(k log k) tiap panggilan — s panjangnya k
    groups[key] = append(groups[key], s)
}

Ciri: ukuran loop luar n, dikalikan biaya bagian dalam k log k.

O(2ⁿ) — rekursi bercabang jadi 2+ panggilan tiap level, tanpa caching

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)   // 2 panggilan rekursif tiap kali
}

Ciri: tidak ada loop sama sekali — pertumbuhannya berasal dari percabangan panggilan rekursif.

n² vs n·m — pasangan yang mudah tertukar

Keduanya terlihat seperti dua nested loop. Bedanya ada pada apa yang di-loop.

// O(n²) — kedua loop melewati koleksi YANG SAMA
for i := range items {
    for j := range items { ... }
}

// O(n·m) — loop melewati DUA koleksi (independen) yang BERBEDA
for i := range listA {   // ukuran n
    for j := range listB { ... }  // ukuran m
}
  • Koleksi/range index sama di kedua loop → satu huruf, dikuadratkan (n²)
  • Hal berbeda dan independen yang di-iterasi → dua huruf, dikalikan (n·m)

Kenapa penting: n=1000, m=5 → n·m = 5.000 (cepat), tapi jika salah dianggap n² = 1.000.000, itu sangat berlebihan menaksir biayanya. Huruf-huruf ini menyimpan informasi nyata tentang input — jangan disatukan hanya karena kodenya terlihat simetris.

Cara menurunkan kompleksitas dari kode

Untuk setiap loop atau pemanggilan rekursif, tanyakan:

  1. Apa yang saya iterasi, dan seberapa besar? → itu jadi sebuah variabel
  2. Apakah ini bersarang di dalam loop lain? → kalikan biayanya
  3. Apakah terjadi berurutan (tidak bersarang)? → jumlahkan biayanya (biasanya cukup ambil suku terbesar)
  4. Apakah memanggil sesuatu yang bukan O(1)? (sort, loop lain, panggilan rekursif) → kalikan biaya itu
for _, s := range strs {        // O(n) — n string
    key := sortString(s)        // O(k log k) — sort di dalam loop
    groups[key] = append(...)   // O(k) amortized
}
// total: O(n · k log k)

Big-O → apa yang dipakai saat coding

Ingin ini Pakai ini
lookup O(1) map / hash table
O(log n) binary search, balanced tree, membagi masalah jadi separuh
O(n) satu pass, atau map untuk menghindari nested loop
O(n log n) sorting, divide-and-conquer
menghindari O(n²) ganti nested loop dengan map — trik klasik menukar memori demi kecepatan

Pola klasik — mengubah O(n²) jadi O(n):

// O(n²): nested loop mengecek setiap pasangan
for i := 0; i < len(nums); i++ {
    for j := i + 1; j < len(nums); j++ {
        if nums[i] == nums[j] { return true }
    }
}

// O(n): map menukar memori demi kecepatan
seen := make(map[int]bool)
for _, x := range nums {
    if seen[x] { return true }
    seen[x] = true
}

Time complexity vs space complexity (eksplisit)

Setiap algoritma punya dua biaya. Big-O bisa menjelaskan salah satunya — selalu periksa yang mana yang sedang dibahas.

Time complexity — berapa banyak operasi seiring n bertambah

Menghitung langkah/operasi, bukan detik di jam dinding.

func sum(nums []int) int {
    total := 0
    for _, x := range nums {   // n langkah
        total += x
    }
    return total
}
// Time: O(n) — satu operasi per elemen
// Space: O(1) — hanya `total` yang ekstra, tidak bertambah seiring n

Space complexity — berapa banyak memori EKSTRA seiring n bertambah

Menghitung memori di luar input itu sendiri — array bantu, map, call stack rekursi, dll. Array input sendiri biasanya tidak dihitung (kecuali diminta untuk dihitung).

func double(nums []int) []int {
    result := make([]int, len(nums))   // array baru, ukuran n
    for i, x := range nums {
        result[i] = x * 2
    }
    return result
}
// Time: O(n) — satu operasi per elemen
// Space: O(n) — `result` adalah array baru yang bertambah seiring n

Waktu sama, memori berbeda (trade-off klasik)

// O(n) time, O(n) SPACE — map ekstra bertambah seiring n
func hasDuplicate(nums []int) bool {
    seen := make(map[int]bool)
    for _, x := range nums {
        if seen[x] { return true }
        seen[x] = true
    }
    return false
}

// O(n log n) time, O(1) SPACE — sort in place, tanpa struktur ekstra
func hasDuplicate(nums []int) bool {
    sort.Ints(nums)
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i-1] { return true }
    }
    return false
}

Masalah sama, dua jawaban valid — satu lebih cepat (time lebih baik), satu lagi memakai memori lebih sedikit (space lebih baik). Tidak ada yang “salah”; memilih salah satu adalah trade-off, bukan soal benar-salah.

Rekursi punya biaya memori TERSEMBUNYI: call stack

func fib(n int) int {
    if n <= 1 { return n }
    return fib(n-1) + fib(n-2)
}
// Time: O(2ⁿ) — panggilan bercabang
// Space: O(n) — BUKAN O(2ⁿ)! Hanya rantai panggilan saat ini (kedalaman n)
//               yang berada di stack sekaligus, bukan semua cabang bersamaan.

Ciri: untuk rekursi, time biasanya bergantung pada total jumlah panggilan (percabangan), sedangkan space biasanya hanya bergantung pada seberapa dalam rekursinya (rantai panggilan terpanjang yang menunggu di stack sekaligus).

Cara cepat mengenali space complexity dalam kode

Tanyakan: “struktur ekstra apa yang saya buat yang ikut membesar jika input membesar?”

  • Slice/array/map baru berukuran n → space O(n)
  • Hanya beberapa variabel (counter, sum, boolean) → space O(1)
  • Fungsi rekursif → space = kedalaman maksimum call stack, bukan total panggilan

Resource fisik mana yang ditekan (CPU vs RAM)

Time dan space complexity bukan cuma matematika abstrak — keduanya berhubungan langsung dengan resource nyata di mesin yang menjalankan kode.

Jenis kompleksitas Resource fisik Apa yang “membesar”
Time complexity CPU Jumlah instruksi yang harus dieksekusi CPU. Lebih banyak operasi = lebih banyak siklus CPU = waktu eksekusi lebih lama.
Space complexity RAM Jumlah memori yang dialokasikan di luar input. Lebih banyak struktur data ekstra = lebih banyak byte yang disimpan di memori sekaligus.

Time complexity = biaya CPU

func sum(nums []int) int {
    total := 0
    for _, x := range nums {   // CPU melakukan tambah-dan-simpan ini, n kali
        total += x
    }
    return total
}

Setiap iterasi loop secara harfiah berarti lebih banyak instruksi yang harus diproses CPU. O(n²) dibanding O(n) berarti CPU bekerja jauh lebih banyak seiring n membesar — itulah sebabnya algoritma O(n²) terasa “lambat”/penggunaan CPU tinggi pada input besar.

Space complexity = biaya RAM

func double(nums []int) []int {
    result := make([]int, len(nums))   // alokasi ini memakan RAM, ukuran n
    for i, x := range nums {
        result[i] = x * 2
    }
    return result
}

result adalah bagian memori di RAM yang ukurannya mengikuti n. Jika n sangat besar, inilah yang menyebabkan error out-of-memory — bukan CPU yang lambat, tapi RAM yang tidak cukup untuk menampung struktur ekstra tersebut.

Kenapa perbedaan ini penting untuk debugging nyata

  • Aplikasi lambat tapi penggunaan memori terlihat normal → kemungkinan masalah time complexity (terlalu banyak operasi CPU, misalnya nested loop O(n²) yang tidak sengaja) → profiling CPU / hitung operasi
  • Aplikasi crash karena out-of-memory, atau penggunaan RAM membengkak → kemungkinan masalah space complexity (terlalu banyak data ekstra yang dialokasikan, misalnya membuat map raksasa atau menduplikasi array) → profiling alokasi memori

Rekursi menekan KEDUANYA, dengan cara berbeda

func fib(n int) int {
    if n <= 1 { return n }
    return fib(n-1) + fib(n-2)
}
  • CPU: O(2ⁿ) — CPU mengeksekusi jumlah panggilan yang eksponensial
  • RAM: O(n) — hanya rantai panggilan saat ini yang berada di stack (memakai memori stack) di satu waktu, bukan semua cabang sekaligus

Jadi sangat mungkin sesuatu itu berat di CPU tapi ringan di RAM (seperti fib naif) atau berat di RAM tapi ringan di CPU (seperti caching setiap hasil yang pernah dihitung untuk menghindari perhitungan ulang).

Pengingat lainnya

  • Big-O biasanya berarti worst case kecuali dinyatakan lain (average/best case bisa berbeda — misalnya quicksort rata-rata O(n log n), worst case O(n²))
  • Operasi berurutan dijumlahkan (O(n) + O(n) = O(n)); operasi bersarang dikalikan
  • Setiap algoritma punya time dan space complexity — hitung juga memori ekstra (map, array bantu, stack rekursi)
  • Beri nama variabel loop sesuai apa yang dihitung (n, k, m) — ini mendokumentasikan kompleksitas sambil menulis kode

Cara membangun kemampuan ini

  1. Pelajari toolkit kecil di atas (~6 bentuk) — jangan hafalkan katalog raksasa
  2. Untuk setiap loop/rekursi yang ditulis, tanyakan “apa yang saya iterasi, seberapa besar, bersarang atau berurutan?”
  3. Latih menurunkan Big-O pada kode yang sudah dipahami sebelum mengecek jawabannya
  4. Saat melihat huruf yang belum familiar, tanyakan apa yang dihitungnya — hampir selalu bisa dijawab dari konteks
  5. Sumber bagus: Grokking Algorithms oleh Aditya Bhargava (visual, ramah untuk pemula)