Big O #

Dalam dunia software engineering, algoritma yang benar saja tidak cukup. Algoritma tersebut juga harus efisien. Di sinilah Big O Notation menjadi konsep fundamental yang wajib dipahami oleh setiap engineer, terutama ketika sistem mulai menangani data besar, traffic tinggi, atau resource terbatas.

Big O bukan sekadar teori akademis — ia adalah alat praktis untuk:

• Memprediksi performa
• Membandingkan solusi
• Menghindari bottleneck sejak awal desain

Artikel ini akan membahas Big O secara konseptual, intuitif, dan praktis, lengkap dengan contoh konkret menggunakan Golang.

Apa Itu Big O Notation? #

Big O Notation adalah cara untuk mengukur kompleksitas algoritma berdasarkan pertumbuhan input (n).

Fokus Big O bukan pada:

• Kecepatan CPU
• Bahasa pemrograman
• Optimasi compiler

Tetapi pada:

Bagaimana performa algoritma bertumbuh ketika input semakin besar.

Big O biasanya digunakan untuk mengukur:

1. Time Complexity → seberapa lama algoritma berjalan
2. Space Complexity → seberapa banyak memori yang digunakan

Tujuan Utama Big O #

Mengukur Skalabilitas #

Algoritma yang cepat di data kecil bisa menjadi bencana di data besar.

Big O membantu menjawab:

“Apa yang terjadi jika data naik 10x atau 100x?”

Membandingkan Alternatif Solusi #

Dengan Big O, kita bisa membandingkan dua solusi tanpa perlu benchmarking terlebih dahulu.

Contoh:

• O(n²) vs O(n log n)
• O(n) vs O(1)

Menghindari Bottleneck Arsitektur #

Kesalahan Big O sering muncul dalam:

• Loop bersarang
• Query database dalam loop
• Validasi data skala besar

Prinsip Dasar Big O #

Worst Case Analysis #

Big O selalu melihat skenario terburuk.

Kenapa? Karena sistem harus tetap stabil meskipun kondisi terburuk terjadi.

Abaikan Konstanta #

O(2n) → O(n) O(100n) → O(n)

Yang penting adalah pola pertumbuhan, bukan angka kecil.

Ambil Dominan Term #

O(n² + n) → O(n²)

Jenis-Jenis Kompleksitas Big O (dengan Contoh Golang) #

O(1) – Constant Time #

Waktu eksekusi tidak berubah, berapa pun ukuran input.

Contoh Golang #

func getFirstElement(arr []int) int {
    return arr[0]
}

Use case nyata:

• Akses map
• Akses array by index
• Cache lookup

O(n) – Linear Time #

Waktu eksekusi sebanding dengan jumlah data.

Contoh Golang #

func sum(arr []int) int {
    total := 0
    for _, v := range arr {
        total += v
    }
    return total
}

Jika data 2x → waktu 2x.

O(n²) – Quadratic Time #

Biasanya muncul dari nested loop.

Contoh Golang #

func printPairs(arr []int) {
    for i := 0; i < len(arr); i++ {
        for j := 0; j < len(arr); j++ {
            fmt.Println(arr[i], arr[j])
        }
    }
}

⚠️ Sangat berbahaya untuk data besar.

O(log n) – Logarithmic Time #

Data dipotong setiap iterasi.

Contoh Golang (Binary Search) #

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
        }
        if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

Sangat efisien untuk data besar.

O(n log n) – Linearithmic Time #

Kombinasi loop dan pembagian data.

Contoh #

• Merge Sort
• Quick Sort (average case)

sort.Ints(arr) // Implementasi O(n log n)

Digunakan hampir di semua sorting modern.

O(2ⁿ) – Exponential Time #

Pertumbuhan sangat ekstrem.

Contoh Golang (Fibonacci Naif) #

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

⚠️ Hindari di production tanpa memoization.

Big O dalam Skenario Nyata Software Engineering #

Loop + Database Query (Anti-Pattern) #

for _, id := range userIDs {
    db.GetUserByID(id) // Query di dalam loop
}

❌ Bisa berubah dari O(n) menjadi O(n × latency DB)

✅ Solusi:

• Batch query
• IN clause
• Cache

Validasi Duplikat Data #

❌ O(n²)

for i := 0; i < len(arr); i++ {
    for j := i + 1; j < len(arr); j++ {
        if arr[i] == arr[j] {
            return true
        }
    }
}

✅ O(n)

seen := make(map[int]bool)
for _, v := range arr {
    if seen[v] {
        return true
    }
    seen[v] = true
}

Big O vs Real Performance #

Big O bukan pengganti benchmarking.

Gunakan Big O untuk:

• Desain awal
• Review kode
• Diskusi arsitektur

Gunakan benchmark untuk:

• Fine tuning
• Membandingkan library
• Performance regression

Kesalahan Umum Engineer Mengenai Big O #

1. Menganggap Big O = kecepatan absolut
2. Mengabaikan memory complexity
3. Over-optimasi di data kecil
4. Tidak mempertimbangkan konteks bisnis

Kapan Harus Peduli Big O? #

✅ Saat:

• Data > ribuan
• Loop bersarang
• Path hot / critical
• Sistem distributed

❌ Tidak wajib saat:

• Script sekali jalan
• Data sangat kecil
• Prototyping awal

Penutup #

Big O adalah alat berpikir, bukan sekadar rumus.

Engineer yang memahami Big O:

• Menulis kode yang scalable
• Menghindari masalah sebelum terjadi
• Membuat keputusan desain yang rasional

Code that works is good. Code that scales is better.