Big O notation adalah cara menulis batas atas pertumbuhan jumlah operasi sebuah algoritma ketika ukuran inputnya membesar. Jadi O(n) tidak berarti “algoritma ini butuh n detik”. Artinya, kalau inputnya dikali dua, jumlah operasinya paling banyak ikut naik kira-kira dua kali. Big O mengukur pola pertumbuhan, bukan waktu eksekusi nyata.

Ini bagian ketiga dari seri Belajar Struktur Data dari Nol. Di Kompleksitas Algoritma: Kenapa Struktur Data Menentukan Performa kita sudah merasakan sendiri bedanya program cepat dan lambat. Sekarang kita kasih nama resmi untuk pola-pola itu, lalu buktikan lewat benchmark Go dengan input 1.000 versus 1.000.000 elemen. Kode di sini dites dengan Go 1.24, tapi jalan di Go 1.22 ke atas.

Enam Kelas Kompleksitas yang Paling Sering Muncul

Hampir semua algoritma di seri ini masuk ke salah satu dari enam kelas berikut, urut dari yang paling lambat tumbuh:

O(1), konstan. Jumlah operasi tidak peduli ukuran input. Contoh: akses elemen slice lewat indeks.
O(log n), logaritmik. Setiap langkah membuang setengah data. Contoh: binary search.
O(n), linear. Sentuh setiap elemen sekali. Contoh: menjumlahkan isi slice.
O(n log n), linearitmik. Kelas terbaik untuk sorting berbasis perbandingan. Contoh: merge sort, quick sort rata-rata.
O(n²), kuadratik. Setiap elemen dibandingkan dengan setiap elemen lain. Contoh: nested loop, bubble sort.
O(2ⁿ), eksponensial. Jumlah operasi berlipat dua setiap input bertambah satu. Contoh: rekursi Fibonacci naif.

Kalau digambar, kurvanya kira-kira begini. Semakin curam, semakin cepat algoritma jadi tidak terpakai untuk data besar:

operasi
|            O(2^n)  O(n^2)
|              |      /     O(n log n)
|              |     /     /      O(n)
|             /    /     /    ___/
|           _/  _/    __/____/     O(log n)
|      ____/__/______/------------ O(1)
+---------------------------------> n

Angka membuat bedanya lebih terasa. Perkiraan jumlah operasi untuk tiga ukuran input:

Kelas	n = 10	n = 1.000	n = 1.000.000
O(1)	1	1	1
O(log n)	3	10	20
O(n)	10	1.000	1.000.000
O(n log n)	33	10.000	20.000.000
O(n²)	100	1.000.000	1.000.000.000.000
O(2ⁿ)	1.024	lebih dari jumlah atom di alam semesta	tidak masuk akal

Perhatikan baris O(n²). Di n = 1.000 masih sejuta operasi, selesai dalam hitungan milidetik. Di n = 1.000.000 sudah satu triliun. Itulah kenapa program yang lancar saat demo bisa mati saat data produksi masuk.

Praktik: Satu Fungsi Go untuk Tiap Kelas Kompleksitas

Buat folder baru, lalu simpan kode berikut sebagai main.go:

package main

import "fmt"

// O(1): berapa pun panjang slice, cuma satu operasi
func Pertama(data []int) int {
	return data[0]
}

// O(log n): setiap iterasi membuang setengah data (data harus terurut)
func BinarySearch(data []int, target int) int {
	low, high := 0, len(data)-1
	for low <= high {
		mid := (low + high) / 2
		if data[mid] == target {
			return mid
		}
		if data[mid] < target {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}

// O(n): sentuh setiap elemen tepat sekali
func Jumlah(data []int) int {
	total := 0
	for _, v := range data {
		total += v
	}
	return total
}

// O(n^2): nested loop, setiap elemen dibandingkan dengan elemen lain
func HitungPasanganNol(data []int) int {
	count := 0
	for i := 0; i < len(data); i++ {
		for j := i + 1; j < len(data); j++ {
			if data[i]+data[j] == 0 {
				count++
			}
		}
	}
	return count
}

// O(2^n): setiap pemanggilan memanggil dirinya dua kali
func FibNaif(n int) int {
	if n < 2 {
		return n
	}
	return FibNaif(n-1) + FibNaif(n-2)
}

func main() {
	data := []int{-3, -1, 0, 1, 3, 5, 8}
	fmt.Println(Pertama(data))            // -3
	fmt.Println(BinarySearch(data, 5))    // 5
	fmt.Println(Jumlah(data))             // 13
	fmt.Println(HitungPasanganNol(data))  // 2
	fmt.Println(FibNaif(10))              // 55
}

Untuk O(n log n) kita pakai sort.Ints dari pustaka standar, yang implementasinya ada di kelas itu. Merge sort dan quick sort buatan sendiri menyusul di bagian 20 dan 21 seri ini.

Jalankan dulu untuk memastikan semuanya benar:

go mod init bigo
go run main.go

Output yang diharapkan:

Benchmark Go: Input 1.000 vs 1.000.000

Sekarang bagian serunya. Kita ukur pola pertumbuhannya pakai fitur benchmark bawaan Go. Simpan sebagai main_test.go di folder yang sama:

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"testing"
)

var hasil int

func buatData(n int) []int {
	data := make([]int, n)
	for i := range data {
		data[i] = rand.Intn(n)
	}
	return data
}

func BenchmarkPertama(b *testing.B) {
	for _, n := range []int{1000, 1000000} {
		data := buatData(n)
		b.Run(fmt.Sprintf("n=%d", n), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				hasil = Pertama(data)
			}
		})
	}
}

func BenchmarkBinarySearch(b *testing.B) {
	for _, n := range []int{1000, 1000000} {
		data := buatData(n)
		sort.Ints(data)
		b.Run(fmt.Sprintf("n=%d", n), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				hasil = BinarySearch(data, -1)
			}
		})
	}
}

func BenchmarkJumlah(b *testing.B) {
	for _, n := range []int{1000, 1000000} {
		data := buatData(n)
		b.Run(fmt.Sprintf("n=%d", n), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				hasil = Jumlah(data)
			}
		})
	}
}

// Sengaja hanya sampai 10.000. Baca penjelasan di bawah.
func BenchmarkHitungPasanganNol(b *testing.B) {
	for _, n := range []int{1000, 10000} {
		data := buatData(n)
		b.Run(fmt.Sprintf("n=%d", n), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				hasil = HitungPasanganNol(data)
			}
		})
	}
}

Variabel hasil di level package itu penting. Tanpa itu, compiler Go bisa membuang pemanggilan fungsi yang hasilnya tidak dipakai, dan benchmark kamu mengukur ruang kosong.

Jalankan:

go test -bench=. -benchtime=1s

Angkanya pasti beda di tiap mesin, tapi polanya akan mirip seperti ini:

BenchmarkPertama/n=1000-8            1000000000    0.25 ns/op
BenchmarkPertama/n=1000000-8         1000000000    0.25 ns/op
BenchmarkBinarySearch/n=1000-8       300000000     4.1 ns/op
BenchmarkBinarySearch/n=1000000-8    150000000     8.3 ns/op
BenchmarkJumlah/n=1000-8             4000000       310 ns/op
BenchmarkJumlah/n=1000000-8          3800          315000 ns/op
BenchmarkHitungPasanganNol/n=1000-8  3000          410000 ns/op
BenchmarkHitungPasanganNol/n=10000-8 28            41000000 ns/op

Baca polanya, bukan angkanya. Pertama tidak berubah walau input naik seribu kali lipat, itu wajah O(1). BinarySearch cuma naik sekitar dua kali karena log₂ 1.000 itu 10 dan log₂ 1.000.000 itu 20. Jumlah naik seribu kali, sebanding dengan inputnya. HitungPasanganNol naik seratus kali padahal inputnya cuma naik sepuluh kali, karena 10² = 100.

Kenapa pasangan nol tidak dites di 1.000.000? Karena itu satu triliun perbandingan per iterasi, benchmark-nya tidak akan selesai dalam waktu masuk akal. FibNaif lebih parah lagi, di n = 50 saja sudah tidak praktis dijalankan.

Cara Membaca Kode dan Menentukan Big O-nya

Loop tunggal berarti O(n)

Satu loop yang menyentuh setiap elemen sekali adalah O(n). Ada dua loop terpisah yang berurutan? Itu O(n + n) = O(2n), yang nanti kita sederhanakan jadi O(n) juga.

Nested loop berarti kalikan

Loop di dalam loop berarti jumlah iterasinya dikalikan. Dua loop yang sama-sama jalan n kali menghasilkan O(n × n) = O(n²). Tiga tingkat berarti O(n³). Hati-hati, ini sering menyelinap lewat pemanggilan fungsi: loop yang di dalamnya memanggil fungsi O(n) juga menghasilkan O(n²), walau di kode kelihatannya cuma satu loop.

Loop yang membagi dua berarti O(log n)

Kalau variabel loop dikali dua atau dibagi dua setiap iterasi, seperti for i := 1; i < n; i *= 2, jumlah iterasinya log₂ n. Sama dengan pola binary search di atas: ruang pencarian dipangkas setengah setiap putaran.

Rekursi: hitung cabangnya

Fungsi rekursif yang memanggil dirinya sekali biasanya O(n). Yang memanggil dirinya dua kali, seperti FibNaif, meledak jadi O(2ⁿ) karena tiap tingkat menggandakan jumlah pemanggilan.

Aturan Penyederhanaan: Buang Konstanta, Ambil Suku Dominan

Big O hanya peduli pola pertumbuhan untuk n yang besar, jadi ada dua aturan penulisan:

Buang konstanta. O(2n + 10) ditulis O(n). O(n/2) juga O(n). Loop yang jalan dua kali tetap linear, cuma linearnya dua kali lebih tebal.
Ambil suku yang paling dominan. O(n² + n + 100) ditulis O(n²). Saat n = 1.000.000, suku n² menyumbang satu triliun operasi sementara suku n cuma sejuta. Sisanya jadi tidak relevan.

Satu pengecualian: dua variabel input yang berbeda jangan digabung. Algoritma yang memproses dua koleksi berbeda ukurannya O(n + m), bukan O(n). Ini muncul lagi nanti di graph, yang kompleksitasnya ditulis O(V + E).

Kesalahan Umum Saat Memakai Big O

Mengira O(1) selalu lebih cepat dari O(n). Salah untuk input kecil. Lookup map itu O(1) tapi ada biaya hashing di tiap akses, jadi scan linear di slice berisi 10 elemen sering lebih cepat karena datanya berdampingan di memori. Big O baru menang bicara saat n membesar.

Menganggap Big O sama dengan waktu eksekusi nyata. Dua algoritma sama-sama O(n) bisa beda kecepatan lima kali lipat karena konstanta yang dibuang tadi. Big O menjawab “bagaimana perilakunya saat data tumbuh”, benchmark menjawab “berapa cepat di mesin ini dengan data ini”. Kamu butuh keduanya. Di proyek klien, tim Arrazy biasanya memakai Big O saat memilih struktur data di tahap desain, lalu memvalidasi titik-titik panas dengan benchmark seperti di atas sebelum sistem naik ke produksi.

Lupa bahwa Big O adalah kasus terburuk yang umum dikutip. Quick sort rata-rata O(n log n) tapi terburuknya O(n²). Map Go rata-rata O(1) tapi terburuknya O(n). Saat membaca “Big O suatu algoritma”, pastikan kamu tahu itu angka rata-rata atau terburuk.

Cheat Sheet Big O untuk Seri Ini

Simpan tabel ini. Semua struktur data dan algoritma di bawah akan kita bedah satu per satu di bagian berikutnya, dan angka-angka ini jadi rujukan kita terus.

Struktur / Algoritma	Akses	Cari	Sisip	Hapus
Array / Slice	O(1)	O(n)	O(n)	O(n)
Singly / Doubly Linked List	O(n)	O(n)	O(1) di ujung	O(1) jika node diketahui
Stack	O(n)	O(n)	O(1) push	O(1) pop
Queue	O(n)	O(n)	O(1) enqueue	O(1) dequeue
Hash Table / map	–	O(1) rata-rata, O(n) terburuk	O(1) rata-rata	O(1) rata-rata
Binary Search Tree (seimbang)	O(log n)	O(log n)	O(log n)	O(log n)
Heap / Priority Queue	O(1) puncak	O(n)	O(log n)	O(log n)

Algoritma	Terbaik	Rata-rata	Terburuk
Bubble Sort / Insertion Sort	O(n)	O(n²)	O(n²)
Merge Sort	O(n log n)	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n log n)	O(n²)
Binary Search	O(1)	O(log n)	O(log n)
BFS / DFS pada graph	O(V + E)

Troubleshooting: Masalah yang Sering Muncul Saat Benchmark

go test bilang “no test files”

Penyebabnya hampir selalu nama file. File benchmark wajib berakhiran _test.go, misalnya main_test.go. Nama seperti benchmark.go atau test_main.go tidak akan dikenali. Pastikan juga kamu menjalankan go test -bench=. di folder yang sama dengan file tersebut, dan go mod init sudah dijalankan.

Hasil benchmark 0.25 ns/op padahal fungsinya berat

Compiler membuang pemanggilan fungsi karena hasilnya tidak pernah dipakai. Ini yang disebut dead code elimination. Solusinya seperti di kode kita: tampung hasil ke variabel level package seperti var hasil int. Untuk O(1) sungguhan seperti Pertama, angka di bawah 1 ns memang normal.

Benchmark tidak pernah selesai atau laptop menggantung

Kamu mungkin memberi input besar ke fungsi O(n²) atau O(2ⁿ). HitungPasanganNol dengan sejuta elemen berarti sekitar satu triliun operasi per iterasi, dan Go akan mencoba mengulanginya berkali-kali. Tekan Ctrl+C, kecilkan inputnya, atau batasi dengan -benchtime=10x agar hanya jalan 10 iterasi.

Fungsi benchmark tidak dijalankan padahal tidak ada error

Nama fungsi harus diawali Benchmark dengan huruf besar dan menerima b *testing.B. Selain itu flag -bench wajib diberi pola, dan titik berarti semua. Tanpa flag itu, go test hanya menjalankan unit test biasa.

Lanjut ke Bagian Berikutnya

Kamu sekarang punya kosakata untuk menilai algoritma: enam kelas kompleksitas, cara membacanya dari kode, aturan penyederhanaannya, plus cheat sheet yang akan terus kita pakai. Di bagian 4, “Array dan Slice di Go: Struktur Data Paling Dasar”, kita buktikan kenapa akses indeks itu O(1) tapi sisip di tengah O(n). Artikelnya terbit menyusul, pantau di halaman hub seri Belajar Struktur Data.

Big O Notation: Cara Mengukur Kompleksitas Algoritma