Big O Notation #

Kode yang benar dan kode yang scalable adalah dua hal yang berbeda. Fungsi yang berjalan sempurna di development dengan 100 data bisa membuat server tersengal di production dengan 1 juta data — bukan karena ada bug, tapi karena algoritmanya tidak dirancang untuk skala besar. Big O Notation adalah bahasa yang digunakan engineer untuk mendiskusikan skalabilitas algoritma: bukan seberapa cepat di kondisi saat ini, melainkan bagaimana pertumbuhannya ketika input bertambah besar. Dengan memahami Big O, kamu bisa mendeteksi bottleneck sebelum terjadi di production, membandingkan dua solusi tanpa harus benchmarking dulu, dan membuat keputusan arsitektur yang rasional berdasarkan data. Artikel ini membahas Big O dari tiga prinsip dasarnya, tujuh kompleksitas yang paling sering ditemui dengan contoh Go konkret, dampak nyata pada data skala besar, space complexity, pola-pola anti-pattern di production, hingga panduan kapan harus dan tidak perlu peduli dengan Big O.

Apa Itu Big O Notation? #

Big O Notation adalah cara untuk mengukur bagaimana kompleksitas sebuah algoritma bertumbuh seiring bertambahnya ukuran input (n). Bukan mengukur waktu dalam detik atau milidetik — melainkan mengukur pola pertumbuhan.

Pertanyaan yang Big O jawab: “Jika data naik 10x, seberapa besar kenaikan waktu/memorinya?”

Big O biasanya mengukur dua hal: time complexity (seberapa lama) dan space complexity (seberapa banyak memori).

flowchart LR
    A["O(1)"] --> B["O(log n)"] --> C["O(n)"] --> D["O(n log n)"] --> E["O(n²)"] --> F["O(n³)"] --> G["O(2ⁿ)"]
    style A fill:#c8e6c9
    style B fill:#dcedc8
    style C fill:#fff9c4
    style D fill:#ffe0b2
    style E fill:#ffccbc
    style F fill:#ffab91
    style G fill:#ef9a9a

Tiga Prinsip Dasar Big O #

1. Worst Case Analysis #

Big O selalu mengukur skenario terburuk — bukan rata-rata, bukan terbaik. Ini masuk akal: sistem harus tetap stabil bahkan di kondisi paling buruk.

// Linear search — best case O(1) jika elemen pertama cocok
// Worst case O(n) jika elemen tidak ada atau di posisi terakhir
func contains(arr []int, target int) bool {
    for _, v := range arr {
        if v == target {
            return true // mungkin ketemu di iterasi pertama
        }
    }
    return false // atau harus scan semuanya — ini yang Big O ukur
}
// Big O: O(n) — karena worst case adalah scan semua elemen

2. Abaikan Konstanta #

O(2n) dan O(100n) keduanya disederhanakan menjadi O(n). Konstanta tidak relevan karena Big O mengukur pola pertumbuhan, bukan nilai absolut.

// O(2n) → O(n)
func twoLoops(arr []int) {
    for _, v := range arr { fmt.Println(v) } // n operasi
    for _, v := range arr { fmt.Println(v) } // n operasi lagi
}
// Total: 2n, tapi tetap O(n) — pertumbuhannya linear

// O(n + 1000) → O(n)
func withConstant(arr []int) {
    for i := 0; i < 1000; i++ { /* setup */ } // konstanta
    for _, v := range arr { process(v) }       // n operasi
}
// Konstanta 1000 tidak relevan saat n sangat besar

3. Ambil Term Dominan #

Ketika ada beberapa term, yang terbesar yang menentukan.

// O(n² + n) → O(n²)
func combined(arr []int) {
    for i := range arr {
        for j := range arr { // n² operasi
            _ = arr[i] + arr[j]
        }
    }
    for _, v := range arr { // n operasi
        fmt.Println(v)
    }
}
// Saat n=1000: n²=1,000,000 vs n=1000
// n diabaikan karena tidak signifikan dibanding n²

Tujuh Kompleksitas yang Paling Sering Ditemui #

O(1) — Constant Time #

Waktu eksekusi tidak berubah berapa pun besarnya input. Ini adalah kompleksitas ideal.

// Semua operasi ini O(1)
func getByIndex(arr []int, i int) int { return arr[i] }   // akses array
func getByKey(m map[string]int, k string) int { return m[k] } // akses map
func stackPush(s *Stack, v int) { s.items = append(s.items, v) } // push

Use case O(1) di production: lookup cache (Redis GET), akses konfigurasi dari map, pengecekan keberadaan key di HashMap/Set, operasi matematika sederhana. Tabel hash (Go map) memberikan O(1) average untuk lookup — ini yang membuat map sangat berguna untuk optimasi.

O(log n) — Logarithmic Time #

Setiap langkah memotong problem menjadi setengahnya. Sangat efisien untuk data besar.

// Binary search — klasik O(log n)
func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1  // buang setengah kiri
        } else {
            high = mid - 1 // buang setengah kanan
        }
    }
    return -1
}

flowchart TD
    A["n = 1.000.000\nlangkah 1"] --> B["n = 500.000\nlangkah 2"]
    B --> C["n = 250.000\nlangkah 3"]
    C --> D["..."]
    D --> E["n = 1\nlangkah ~20"]

Dampak nyata O(log n): n=1.000.000 → hanya ~20 langkah. n=1.000.000.000 → hanya ~30 langkah. Pertumbuhan sangat lambat — hampir constant untuk skala praktis.

Use case O(log n) di production: binary search pada sorted array, operasi di balanced BST (AVL, Red-Black), heap operations, database index traversal (B-tree).

O(n) — Linear Time #

Waktu tumbuh sebanding dengan jumlah data. Setiap elemen dikunjungi sekali.

// Linear scan — O(n)
func sum(arr []int) int {
    total := 0
    for _, v := range arr { total += v } // setiap elemen dikunjungi sekali
    return total
}

func findMax(arr []int) int {
    max := arr[0]
    for _, v := range arr[1:] {
        if v > max { max = v }
    }
    return max
}

O(n) biasanya acceptable kecuali untuk operasi yang dipanggil sangat sering (hot path) atau n sangat besar (jutaan+).

O(n log n) — Linearithmic Time #

Kombinasi linear dan logarithmic. Ini adalah kompleksitas terbaik yang bisa dicapai untuk general-purpose sorting.

// sort.Slice di Go menggunakan introsort — O(n log n)
sort.Slice(users, func(i, j int) bool {
    return users[i].Name < users[j].Name
})

// Merge Sort — klasik O(n log n)
func mergeSort(arr []int) []int {
    if len(arr) <= 1 { return arr }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])   // O(log n) pembagian
    right := mergeSort(arr[mid:])
    return merge(left, right)      // O(n) merge
}
// Total: O(n log n)

O(n²) — Quadratic Time #

Hampir selalu muncul dari nested loop — setiap elemen dipasangkan dengan setiap elemen lain. Harus dihindari untuk data besar.

// ANTI-PATTERN: bubble sort — O(n²)
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n; i++ {
        for j := 0; j < n-i-1; j++ { // nested loop!
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

// ANTI-PATTERN: cek duplikasi dengan nested loop — O(n²)
func hasDuplicateNaive(arr []int) bool {
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ { // nested!
            if arr[i] == arr[j] { return true }
        }
    }
    return false
}

// BENAR: gunakan map untuk O(n)
func hasDuplicate(arr []int) bool {
    seen := make(map[int]bool)
    for _, v := range arr {
        if seen[v] { return true }
        seen[v] = true
    }
    return false
}

Dampak nyata O(n²): n=1.000 → 1 juta operasi. n=10.000 → 100 juta operasi. n=100.000 → 10 miliar operasi. Untuk data production yang bisa mencapai ratusan ribu, O(n²) adalah bencana.

O(n³) dan Beyond #

Tiga nested loop menghasilkan O(n³). Jarang ditemui di business logic, tapi muncul di algoritma matematika tertentu.

// O(n³) — matrix multiplication naif
func matMul(a, b [][]int) [][]int {
    n := len(a)
    result := make([][]int, n)
    for i := range result { result[i] = make([]int, n) }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            for k := 0; k < n; k++ { // tiga nested loop
                result[i][j] += a[i][k] * b[k][j]
            }
        }
    }
    return result
}
// n=100: 1 juta operasi
// n=1000: 1 miliar operasi

O(2ⁿ) — Exponential Time #

Setiap penambahan satu unit input menggandakan waktu komputasi. Tidak bisa digunakan di production untuk input yang cukup besar tanpa optimasi.

flowchart TD
    F5["fib(5)"] --> F4a["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4a --> F3b["fib(3)"]
    F4a --> F2a["fib(2)"]
    F3a --> F2b["fib(2)"]
    F3a --> F1a["fib(1)"]
    F3b --> F2c["fib(2)"]
    F3b --> F1b["fib(1)"]
    Note["Pohon rekursi tumbuh\neksponensial — banyak\nsubproblem dihitung berulang"]

// ANTI-PATTERN: Fibonacci naif — O(2ⁿ)
// fib(n) memanggil fib(n-1) dan fib(n-2) secara rekursif
// Menghasilkan pohon rekursi yang tumbuh eksponensial
func fibNaive(n int) int {
    if n <= 1 { return n }
    return fibNaive(n-1) + fibNaive(n-2)
}
// fib(50) membutuhkan ~1 triliun operasi!

// BENAR: Fibonacci dengan memoization — O(n)
func fibMemo(n int, memo map[int]int) int {
    if n <= 1 { return n }
    if val, ok := memo[n]; ok { return val } // sudah dihitung sebelumnya
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
    return memo[n]
}

// Atau iteratif — O(n) time, O(1) space
func fibIterative(n int) int {
    if n <= 1 { return n }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

Perbandingan Dampak Nyata #

Tabel ini menunjukkan mengapa pemilihan algoritma penting di production:

Artinya: kode dengan O(n²) yang “berjalan cepat” di local dengan 100 data akan membutuhkan waktu 10 miliar kali lebih lama di production dengan 100.000 data dibanding algoritma O(n).

Space Complexity — Yang Sering Diabaikan #

Big O tidak hanya tentang waktu — space complexity sama pentingnya, terutama di lingkungan dengan memori terbatas seperti mobile atau serverless.

// O(n) space — menyimpan semua elemen di memori
func getAllUsers(db Database) []User {
    return db.Query("SELECT * FROM users") // bisa jutaan rows!
}

// BENAR — O(1) space dengan streaming/pagination
func processAllUsers(db Database, process func(User)) {
    offset := 0
    batchSize := 1000
    for {
        users := db.Query("SELECT * FROM users LIMIT ? OFFSET ?", batchSize, offset)
        if len(users) == 0 { break }
        for _, u := range users { process(u) }
        offset += batchSize
    }
}

// Memoization trade-off: O(n) space untuk mendapat O(n) time
// (vs O(2ⁿ) time tanpa memoization)
memo := make(map[int]int) // O(n) space
result := fibMemo(50, memo) // O(n) time — trade space untuk speed

Pola Anti-Pattern di Production #

N+1 Query — O(n) Database Calls #

Ini adalah salah satu anti-pattern O(n) yang paling sering menyebabkan masalah production.

flowchart TD
    subgraph NPlus1["❌ N+1 Query"]
        Q1["SELECT * FROM users\n(1 query)"] --> L1["for setiap user:"]
        L1 --> Q2["SELECT * FROM orders\nWHERE user_id = ?\n(1000 query)"]
        Q2 --> T1["Total: 1001 queries"]
    end
    subgraph Join["✅ Single JOIN"]
        Q3["SELECT u.*, o.*\nFROM users u\nLEFT JOIN orders o\n(1 query)"] --> T2["Total: 1 query"]
    end

// ANTI-PATTERN: N+1 query — O(n) database calls
func getUsersWithOrders(db Database) []UserWithOrders {
    users := db.Query("SELECT * FROM users") // 1 query
    result := make([]UserWithOrders, 0, len(users))

    for _, user := range users {
        orders := db.Query("SELECT * FROM orders WHERE user_id = ?", user.ID)
        // ← N additional queries! Jika ada 1000 user = 1001 total queries
        result = append(result, UserWithOrders{User: user, Orders: orders})
    }
    return result
}

// BENAR: satu query dengan JOIN — O(1) database calls
func getUsersWithOrdersOptimized(db Database) []UserWithOrders {
    rows := db.Query(`
        SELECT u.*, o.*
        FROM users u
        LEFT JOIN orders o ON u.id = o.user_id
    `) // 1 query saja
    return buildUserOrderMap(rows)
}

Cek Duplikasi — O(n²) vs O(n) #

// ANTI-PATTERN: O(n²) — nested loop
func findDuplicateEmails(emails []string) []string {
    var duplicates []string
    for i := 0; i < len(emails); i++ {
        for j := i + 1; j < len(emails); j++ { // O(n²)
            if emails[i] == emails[j] {
                duplicates = append(duplicates, emails[i])
            }
        }
    }
    return duplicates
}

// BENAR: O(n) — gunakan map sebagai counter
func findDuplicateEmailsOptimized(emails []string) []string {
    count := make(map[string]int)
    for _, email := range emails { count[email]++ }

    var duplicates []string
    for email, c := range count {
        if c > 1 { duplicates = append(duplicates, email) }
    }
    return duplicates
}

String Concatenation dalam Loop — O(n²) tersembunyi #

// ANTI-PATTERN: string concatenation dalam loop — O(n²) karena immutable string
func buildCSV(records []string) string {
    result := ""
    for _, r := range records {
        result += r + "," // setiap concatenation membuat string baru!
    }
    return result
}

// BENAR: strings.Builder — O(n)
func buildCSVOptimized(records []string) string {
    var sb strings.Builder
    for _, r := range records {
        sb.WriteString(r)
        sb.WriteByte(',')
    }
    return sb.String()
}

Big O untuk Struktur Data Umum #

Memilih struktur data yang tepat adalah bagian dari keputusan Big O.

Implikasi praktis: jika kamu sering melakukan lookup “apakah X ada di collection?”, gunakan map[T]bool bukan []T. Lookup di slice adalah O(n), di map adalah O(1).

// ANTI-PATTERN: contains check di slice — O(n) per check
allowedRoles := []string{"admin", "manager", "editor"}
func isAllowed(role string) bool {
    for _, r := range allowedRoles { // O(n) setiap kali
        if r == role { return true }
    }
    return false
}

// BENAR: gunakan map — O(1) per check
allowedRoles := map[string]bool{
    "admin":   true,
    "manager": true,
    "editor":  true,
}
func isAllowed(role string) bool {
    return allowedRoles[role] // O(1)
}

Kapan Harus Peduli Big O #

Tidak semua kode perlu dianalisis dengan Big O — ini adalah panduan praktis kapan ia relevan.

flowchart TD
    A[Kode yang ditulis] --> B{"Data > ribuan record?\nLoop bersarang?\nHot path?\nBackground job dataset besar?"}
    B -- Ya --> C["✓ Analisis Big O\nWAJIB"]
    B -- Tidak --> D{"Script sekali jalan?\nPrototyping?\nSudah jelas O(1)/O(log n)?\nKode startup sekali?"}
    D -- Ya --> E["✗ Tidak perlu analisis\nmendalam"]
    D -- Tidak --> F["Profil dulu sebelum\nmemutuskan optimasi"]

Jangan over-optimasi. Kode yang di-optimasi secara agresif sebelum ada data nyata sering kali lebih sulit dibaca dan dipelihara, padahal masalah performanya mungkin tidak pernah terjadi. Profil dulu, optimasi kemudian. Big O membantu menghindari kesalahan yang jelas-jelas buruk — bukan alasan untuk pre-mature optimization.

Checklist Analisis Big O #

ANALISIS:
  □ Identifikasi nested loop yang melibatkan data dari user/database
  □ Cek setiap "contains" atau "lookup" — apakah pakai slice atau map?
  □ Cek string concatenation di dalam loop
  □ Cek query database di dalam loop (N+1 pattern)

OPTIMASI:
  □ Ganti nested loop dengan map lookup jika memungkinkan
  □ Ganti N+1 query dengan JOIN atau batch query
  □ Gunakan strings.Builder untuk concatenation berulang
  □ Pertimbangkan memoization untuk fungsi rekursif berulang

SPACE:
  □ Dataset besar diproses dengan streaming/pagination, bukan load all
  □ Trade-off space vs time (memoization) sudah dipertimbangkan

VALIDASI:
  □ Profiling dilakukan sebelum optimasi (bukan asumsi)
  □ Benchmark sebelum dan sesudah optimasi untuk data realistis
  □ Optimasi tidak mengurangi keterbacaan kode secara signifikan

Ringkasan #

• Big O mengukur pola pertumbuhan kompleksitas, bukan kecepatan absolut — pertanyaannya: “jika data 10x lebih besar, seberapa lambat?”
• Tiga prinsip: worst case analysis, abaikan konstanta, ambil term dominan.
• Tujuh kompleksitas dari terbaik ke terburuk: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(n³) → O(2ⁿ).
• Map untuk O(1) lookup: setiap kali ada “cek apakah X ada di list”, ganti []T dengan map[T]bool.
• N+1 query adalah O(n) database calls yang menyebabkan masalah production — gunakan JOIN atau batch query.
• Nested loop = O(n²): hampir selalu bisa dihindari dengan menggunakan map sebagai lookup table.
• String concatenation dalam loop = O(n²) tersembunyi — gunakan strings.Builder atau bytes.Buffer.
• Space complexity sama pentingnya: hindari memuat seluruh dataset ke memori, gunakan pagination/streaming.
• Memoization mengubah O(2ⁿ) menjadi O(n) dengan trade-off O(n) space — klasik time-space tradeoff.
• Profil sebelum optimasi: Big O membantu menghindari kesalahan yang jelas, bukan alasan untuk pre-mature optimization.

← Sebelumnya: Unit Test   Berikutnya: Jitter →