Big-O Notation
Big-O Notation (Notasi Kompleksitas Waktu)
Big-O sederhananya adalah sebuah metodologi yang dipakai untuk menyatakan berapa banyak operasi (kira-kira) yang dibutuhkan sebuah algoritma ketika input n membesar. Ini juga berarti kita ingin menghitung kompleksitas dari sebuah kode. Ada dua dimensi dalam menghitung kompleksitas kode. Pertama adalah kompleksitas ruang atau space complexity yang berkaitan dengan berapa banyak ruang yang digunakan seperti memori ataupun harddisk komputer. Kedua adalah kompleksitas waktu atau time complexity yang berkaitan berapa lama baris kode dijalankan.
Kenapa dibutuhkan sebuah metode untuk menghitung efisiensi kode? Karena kita tidak bisa hanya mengatakan bahwa kumpulan kode ini dapat dijalankan selama lima detik. Padahal sangat banyak faktor penentu lainnya seperti jumlah datanya, koneksi, latensi, jumlah memori, kecepatan prosesor dan masih banyak yang lainnya.
1. O(1) — Konstan
Waktu eksekusi tidak tergantung ukuran input.
Mau input 10, 1000, atau 1 juta, waktunya tetap sama.
Contoh:
func getFirstElement(arr []int) int {
return arr[0] // langsung ambil index 0
}Perhitungan:
Input:
[5, 8, 10, 20](4 elemen)Langkah: tetap 1.
Input 1 juta elemen → tetap 1 langkah.
👉 O(1) = selalu sama.
2. O(log n) — Logaritmik
Biasanya muncul saat data dipotong setengah-setengah setiap langkah (divide and conquer).
Contoh: Binary Search.
Contoh:
Cari angka 32 di array terurut [1..64].
func binarySearch(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
mid := (left + right) / 2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}Perhitungan:
n = 64
log₂(64) = 6
Jadi maksimal 6 langkah ketemu.
Kalau n = 1 juta → log₂(1.000.000) ≈ 20 langkah aja!
👉 Super cepat, karena selalu potong setengah.
3. O(n) — Linear
Waktu eksekusi bertambah sebanding dengan jumlah input.
Contoh: Linear Search (cari elemen di array tanpa urutan).
Contoh:
func linearSearch(arr []int, target int) int {
for i, v := range arr {
if v == target {
return i
}
}
return -1
}Perhitungan:
n = 10 → maksimal 10 langkah.
n = 1.000.000 → maksimal 1 juta langkah.
👉 Cocok kalau data kecil, tapi lambat untuk data besar.
4. O(n log n) — Linearithmic
Muncul saat algoritma memproses semua elemen (n) lalu juga melakukan pembagian log n kali.
Contoh: Merge Sort, Quick Sort (average case), Heap Sort.
Contoh:
Urutkan 8 elemen dengan Merge Sort.
Perhitungan:
n = 8
log₂(8) = 3
Total langkah ≈ 8 × 3 = 24
n = 1000 → log₂(1000) ≈ 10 → total ≈ 10.000 langkah
Jauh lebih cepat dari O(n²).
👉 Sorting optimal biasanya O(n log n).
5. O(n²) — Kuadratik
Biasanya muncul saat ada nested loop (perulangan dalam perulangan).
Contoh: Bubble Sort, Selection Sort, Insertion Sort (worst case).
Contoh:
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n; i++ {
for j := 0; j < n-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}Perhitungan:
n = 10 → 100 langkah
n = 1000 → 1.000.000 langkah
n = 1 juta → 1 triliun langkah ❌
👉 Cepat untuk data kecil, tapi nggak realistis untuk data besar.
6. O(n³) — Kubik
Lebih parah dari kuadrat → muncul kalau ada 3 nested loop.
Contoh: operasi pada matriks 3D atau triple-nested loop.
Contoh:
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
for k := 0; k < n; k++ {
// operasi
}
}
}Perhitungan:
n = 10 → 1000 langkah
n = 1000 → 1 milyar langkah ❌
👉 Hampir mustahil untuk input besar.
7. O(2ⁿ) — Eksponensial
Waktu eksekusi meledak sangat cepat.
Biasanya muncul di algoritma brute-force untuk kombinasi/subset.
Contoh: Traveling Salesman Problem (brute force), Fibonacci rekursif tanpa memoization.
Contoh (Fibonacci naive):
func fib(n int) int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2)
}Perhitungan:
n = 10 → 2¹⁰ = 1024 langkah
n = 50 → 2⁵⁰ ≈ 1,125 triliun langkah ❌
👉 Cepat meledak, tidak cocok untuk data besar.
8. O(n!) — Faktorial
Kompleksitas paling parah.
Muncul di masalah permutasi (coba semua urutan).
Contoh: brute-force Travelling Salesman Problem (TSP).
Perhitungan:
n = 5 → 5! = 120 langkah
n = 10 → 10! = 3.628.800 langkah
n = 20 → 20! ≈ 2,4 kuadriliun ❌
👉 Sangat tidak efisien, hanya bisa dipakai untuk n kecil.
Urutan dari Cepat → Lambat
O(1) → Konstan
O(log n) → Logaritmik
O(n) → Linear
O(n log n) → Linearithmic
O(n²) → Kuadratik
O(n³) → Kubik
O(2ⁿ) → Eksponensial
O(n!) → Faktorial
Analogi Sederhana
Bayangkan kamu punya daftar 1000 nama:
O(1): Langsung ambil nama pertama → butuh 1 detik.
O(log n): Tanya "apakah nama ini lebih besar/kecil?" (binary search) → butuh ±10 detik.
O(n): Cek satu-satu sampai ketemu → butuh 1000 detik.
O(n log n): Urutkan daftar dulu → butuh ±10.000 detik.
O(n²): Bandingkan setiap orang dengan semua orang → butuh 1.000.000 detik.
O(2ⁿ): Coba semua kombinasi grup nama → gila-gilaan, butuh milyaran tahun.
O(n!): Coba semua urutan duduk → lebih parah lagi, nggak bakal selesai.
Last updated