Fundamental

Big O Notation — How to Talk About Algorithm Performance

Big O Notation is a way to measure the efficiency of an algorithm based on input size. From O(1) to O(n!), understand the complexity classes you most often encounter in everyday coding.

Muhammad Amien·Jul 1, 2026·7 min read

Big O Notation — How to Talk About Algorithm Performance

Bayangin lo punya dua fungsi sorting. Satu selesai dalam 0.5 detik buat 100 item. Satunya lagi 10 detik. Mana yang lo pake? Yang 0.5 detik, jelas.

Tapi gimana kalau datanya 1 juta item? Fungsi pertama tiba-tiba jadi 5 jam. Fungsi kedua cuma 2 detik. Di sinilah Big O Notation jadi penting — bukan cuma soal seberapa cepat kode jalan sekarang, tapi gimana performanya tumbuh seiring data bertambah.

Big O — Bukan Soal Detik, Tapi Soal Pertumbuhan

Big O Notation adalah cara ngukur efisiensi algoritma berdasarkan input size (n). Bukan ngukur waktu eksekusi dalam detik — karena detik beda-beda tergantung hardware, bahasa, dan beban server. Big O ngukur gimana jumlah operasi bertambah saat n membesar.

Ada 3 notasi yang lo bakal temui:

Big O (O) — batas atas. Worst case. Paling sering dipake. "Algoritma ini gak bakal lebih lambat dari O(n²)."

Big Omega (Ω) — batas bawah. Best case. "Minimal, algoritma ini butuh Ω(n) operasi."

Big Theta (Θ) — exact bound. Average case. "Algoritma ini selalu Θ(n log n), gak peduli input-nya."

Dalam praktik, lo cukup paham Big O. Sisanya bonus.

Complexity Classes — dari Konstan sampai Faktorial

Ini hierarki complexity classes yang paling umum, dari paling efisien ke paling lambat:

Makin ke bawah, makin gak praktis buat n besar. O(n²) masih ok buat n=100 (10.000 operasi). Tapi O(2ⁿ) buat n=100? Angka-nya lebih besar dari atom di alam semesta.

O(1) — Constant Time: Gak Peduli Seberapa Besar Input-nya

O(1) artinya jumlah operasi tetap, berapapun n-nya. Akses array by index, hash table lookup, push/pop di stack — semua O(1).

Coba liat kodenya:

Gak peduli array-nya 10 item atau 10 juta — akses index ke-5 selalu butuh 1 operasi. Ini holy grail efisiensi. Tapi gak semua operasi bisa O(1).

O(log n) — Logarithmic: Setiap Langkah Potong Setengah

Logarithmic time artinya setiap iterasi, input size-nya dipotong setengah. Binary search adalah contoh klasik.

Bayangin lo nyari nomor telepon di buku telpon setebal 1000 halaman. Lo gak bakal baca halaman 1 sampai 1000 satu-satu. Lo buka tengah, liat apakah target di kiri atau kanan, terus ulang. Setiap langkah, sisa halaman tinggal setengah.

Dengan 1 miliar item, binary search butuh cuma ~30 langkah (log₂ 1.000.000.000 ≈ 30). Linear search butuh 1 miliar langkah. Ini beda antara 30 detik dan 30 tahun.

O(n) — Linear: Sebanding dengan Input

O(n) artinya jumlah operasi tumbuh linear dengan n. Satu loop dari 0 sampai n — itu O(n). Dua loop terpisah (bukan nested) — tetap O(n), karena 2n ≈ n dalam Big O.

Linear search, array traversal, menghitung total — semua O(n). Ini baseline yang wajar. Kalau algoritma lo O(n), lo masih aman buat jutaan item.

O(n log n) — Linearithmic: Sweet Spot Sorting

O(n log n) adalah complexity terbaik yang bisa dicapai oleh comparison-based sorting algorithm. Merge sort, quick sort (average case), heap sort — semua O(n log n).

Kenapa gak bisa lebih cepat? Karena comparison-based sorting butuh minimal n log n perbandingan untuk n item. Ini udah dibuktikan secara matematis — namanya comparison sort lower bound.

Merge sort bagi array jadi dua (log n level), dan di setiap level butuh n operasi buat merge. Hasilnya n × log n. Buat 1 juta item, ini sekitar 20 juta operasi — reasonable.

O(n²) — Quadratic: Hati-hati dengan Nested Loop

O(n²) artinya operasi tumbuh kuadratik. Satu loop di dalam loop lain — setiap n item, lo bandingin dengan n item lainnya. Bubble sort, selection sort, insertion sort — semua O(n²).

Buat n=10.000, bubble sort butuh 100 juta operasi. Masih ok. Tapi buat n=1 juta? 1 triliun operasi. Gak bakal kelar dalam hidup lo. Makanya sorting library pake O(n log n), bukan O(n²).

O(2ⁿ) dan O(n!) — Jangan Sampai Ke sini

Exponential dan factorial time adalah zona bahaya. Fibonacci recursive tanpa memoization itu O(2ⁿ). Traveling salesman brute force itu O(n!).

Fib(50) tanpa memoization? Gak bakal kelar. Fib(50) dengan memoization? Instant. Bedanya O(2ⁿ) vs O(n) — cuma karena nyimpen hasil yang udah dihitung.

Ini pelajaran penting: algoritma yang sama, implementasi beda, complexity bisa beda drastis. Rekursi tanpa cache itu jebakan.

Aturan Praktis — Cara Cepat Tebak Big O

Gak perlu hafalin semua. Cukup liat struktur kode lo:

Satu loop dari 0 ke n → O(n). Dua loop terpisah (bukan nested) → tetap O(n). Loop nested → O(n²). Loop yang tiap iterasi potong setengah → O(log n). Rekursi dengan 2 cabang per level → O(2ⁿ).

Tapi ada yang lebih penting dari Big O: constant factor. Kadang O(n²) dengan n kecil lebih cepat dari O(n log n) dengan overhead tinggi. Quick sort O(n²) worst case, tapi di praktik lebih cepat dari merge sort karena constant factor-nya lebih kecil.

Big O ngasih lo bahasa buat diskusi performa. Tapi benchmark di hardware lo sendiri tetap yang paling valid.

Penutup — Big O Itu Bahasa, Bukan Agama

Big O Notation bukan alat buat ngukur milidetik. Ini alat buat ngomongin gimana algoritma lo berskala. Lo gak perlu hafal semua complexity class. Tapi lo perlu bisa liat kode dan bilang: "Ini O(n²), bakal jebol kalau datanya gede."

Mulai dari yang paling sering lo temui: O(1), O(n), O(n log n), O(n²). Sisanya — O(log n), O(2ⁿ), O(n!) — bakal lo temui pas lo butuh. Dan inget: algoritma O(n) dengan implementasi bagus lebih baik dari algoritma O(log n) yang buggy.