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. Panduan 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?"
O(1) → data 10x → waktu tetap sama
O(log n) → data 10x → waktu +1 langkah
O(n) → data 10x → waktu 10x
O(n log n)→ data 10x → waktu ~33x
O(n²) → data 10x → waktu 100x
O(2ⁿ) → data +1 → waktu 2x
Big O biasanya mengukur dua hal: time complexity (seberapa lama) dan space complexity (seberapa banyak memori).
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
}
// 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.
// 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:
Kompleksitas n=10 n=100 n=1,000 n=100,000
──────────── ────── ───────── ─────────── ──────────────────
O(1) 1 1 1 1
O(log n) 3 7 10 17
O(n) 10 100 1,000 100,000
O(n log n) 33 700 10,000 1,700,000
O(n²) 100 10,000 1,000,000 10,000,000,000
O(2ⁿ) 1,024 1.27×10³⁰ (astronomis) (tidak mungkin)
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.
// 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.
Operasi Array/Slice Map (Hash) Sorted Array BST (balanced)
──────────────── ─────────── ────────── ──────────── ──────────────
Access by index O(1) - O(1) -
Search O(n) O(1) avg O(log n) O(log n)
Insert (end) O(1) amort O(1) avg O(n) O(log n)
Insert (middle) O(n) - O(n) O(log n)
Delete O(n) O(1) avg O(n) O(log n)
Contains/Exists O(n) O(1) avg O(log n) O(log n)
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.
WAJIB dianalisis:
✓ Data lebih dari ribuan record
✓ Loop bersarang yang melibatkan data dari user/database
✓ Hot path — kode yang dipanggil ratusan kali per detik
✓ Background job yang memproses seluruh dataset
✓ Query atau operasi yang tumbuh seiring jumlah user
TIDAK perlu dianalisis secara mendalam:
✗ Script sekali jalan dengan data kecil
✗ Prototyping / proof of concept
✗ Operasi yang sudah jelas O(1) atau O(log n)
✗ Kode yang hanya dijalankan saat startup (sekali)
✗ Optimasi premature sebelum ada data penggunaan nyata
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.
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
[]Tdenganmap[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.Builderataubytes.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.