Mengenal Big O Notation: Cara Mengukur Efisiensi Algoritma

Pendahuluan

Bayangkan kamu diminta mencari nama seseorang di buku telepon. Ada dua cara yang bisa kamu lakukan: pertama, baca satu per satu dari halaman pertama sampai ketemu. Kedua, langsung buka bagian tengah, lihat apakah nama yang dicari ada di atas atau bawah, lalu ulangi prosesnya.

Cara pertama dan kedua sama-sama akan menemukan nama yang kamu cari — tapi mana yang lebih cepat? Di sinilah Big O Notation berperan.

Big O Notation adalah bahasa universal yang digunakan programmer untuk mengukur seberapa efisien sebuah algoritma. Bukan dalam satuan detik (karena itu bergantung pada hardware), melainkan dalam satuan jumlah langkah relatif terhadap ukuran input. Dengan memahami Big O, kamu bisa menulis kode yang tidak hanya benar, tapi juga cepat dan skalabel.

Apa Itu Notasi Big O?

Big O Notation menggambarkan worst-case scenario dari sebuah algoritma — seberapa buruk performanya dalam kondisi paling tidak menguntungkan. Notasinya ditulis sebagai O(sesuatu), di mana “sesuatu” adalah fungsi yang menggambarkan pertumbuhan jumlah operasi.

Analogi sederhana: kamu punya lemari pakaian.

• Jika mencari kaos tertentu dengan mengecek satu per satu, semakin banyak pakaian = semakin lama.
• Jika pakaian sudah diurutkan dan dilabeli, pencarian jadi jauh lebih cepat.

Big O mengukur “seberapa lambat pencarian bertambah ketika lemarinya makin penuh.”

Konsep Kunci

N = ukuran input (jumlah elemen, jumlah data, dll)
O(f(N)) = jumlah operasi tumbuh sebanding dengan f(N)

Hal penting yang perlu diingat:

• Big O mengabaikan konstanta — O(2N) ditulis sebagai O(N)
• Big O mengabaikan suku kecil — O(N² + N) ditulis sebagai O(N²)
• Kita fokus pada bagaimana pertumbuhan terjadi, bukan nilai absolutnya

Jenis-jenis Notasi Big O yang Umum

1. O(1) — Constant Time

Jumlah operasi tidak berubah meskipun ukuran input bertambah. Ini adalah yang paling ideal.

def ambil_elemen_pertama(data):
    return data[0]  # Selalu 1 langkah, tidak peduli panjang list

angka = [10, 20, 30, 40, 50]
print(ambil_elemen_pertama(angka))  # Output: 10

Analogi: Mengambil buku dari rak jika kamu tahu persis posisinya. Satu langkah, selesai.

2. O(log N) — Logarithmic Time

Setiap langkah memotong setengah jumlah kemungkinan. Sangat efisien untuk data besar.

def binary_search(data, target):
    kiri, kanan = 0, len(data) - 1
    
    while kiri <= kanan:
        tengah = (kiri + kanan) // 2
        
        if data[tengah] == target:
            return tengah
        elif data[tengah] < target:
            kiri = tengah + 1
        else:
            kanan = tengah - 1
    
    return -1

angka_terurut = [1, 3, 5, 7, 9, 11, 13, 15]
posisi = binary_search(angka_terurut, 7)
print(f"Angka 7 ditemukan di indeks: {posisi}")  # Output: 3

Analogi: Kembali ke buku telepon tadi — buka tengah, potong setengah, ulangi. Untuk 1 juta nama, hanya butuh sekitar 20 langkah!

3. O(N) — Linear Time

Jumlah operasi berbanding lurus dengan ukuran input. Dua kali lipat data = dua kali lipat waktu.

def cari_nilai(data, target):
    for i, nilai in enumerate(data):
        if nilai == target:
            return i
    return -1

buah = ["apel", "mangga", "jeruk", "pisang", "durian"]
posisi = cari_nilai(buah, "pisang")
print(f"Pisang ditemukan di indeks: {posisi}")  # Output: 3

Analogi: Mencari kunci yang hilang dengan mengecek tiap laci satu per satu dari awal.

4. O(N log N) — Linearithmic Time

Lebih lambat dari O(N) tapi jauh lebih baik dari O(N²). Ini adalah kompleksitas algoritma sorting yang efisien seperti Merge Sort dan Quick Sort.

def merge_sort(data):
    if len(data) <= 1:
        return data
    
    tengah = len(data) // 2
    kiri = merge_sort(data[:tengah])
    kanan = merge_sort(data[tengah:])
    
    return gabung(kiri, kanan)

def gabung(kiri, kanan):
    hasil = []
    i = j = 0
    
    while i < len(kiri) and j < len(kanan):
        if kiri[i] <= kanan[j]:
            hasil.append(kiri[i])
            i += 1
        else:
            hasil.append(kanan[j])
            j += 1
    
    hasil.extend(kiri[i:])
    hasil.extend(kanan[j:])
    return hasil

angka = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(angka))  # Output: [3, 9, 10, 27, 38, 43, 82]

5. O(N²) — Quadratic Time

Untuk setiap elemen, kita memproses semua elemen lainnya. Biasanya muncul pada nested loop.

def bubble_sort(data):
    n = len(data)
    for i in range(n):          # Loop luar: N kali
        for j in range(n - i - 1):  # Loop dalam: ~N kali
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data

angka = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(angka))  # Output: [11, 12, 22, 25, 34, 64, 90]

Analogi: Membandingkan setiap siswa dengan setiap siswa lain untuk menentukan peringkat. 100 siswa = 10.000 perbandingan.

6. O(2^N) — Exponential Time

Setiap penambahan satu elemen menggandakan jumlah operasi. Sangat lambat dan harus dihindari untuk input besar.

def fibonacci_lambat(n):
    if n <= 1:
        return n
    return fibonacci_lambat(n - 1) + fibonacci_lambat(n - 2)

# Hati-hati: jangan panggil dengan n > 35, akan sangat lambat!
print(fibonacci_lambat(10))  # Output: 55

Perbandingan Visual

Untuk N = 16 elemen:

Aturan Praktis dalam Menghitung Big O

Aturan 1: Abaikan Konstanta

def cetak_dua_kali(data):
    for item in data:      # O(N)
        print(item)
    
    for item in data:      # O(N)
        print(item)
    
    # Total: O(2N) → disederhanakan menjadi O(N)

Aturan 2: Ambil yang Dominan

def campuran(data):
    # O(1) — konstanta
    print("Mulai proses")
    
    # O(N) — linear
    for item in data:
        print(item)
    
    # O(N²) — kuadratik
    for i in data:
        for j in data:
            print(i, j)
    
    # Total: O(1 + N + N²) → ambil dominan = O(N²)

Aturan 3: Loop Bersarang = Kalikan

# Loop independen → tambahkan
def independen(data_a, data_b):
    for a in data_a:  # O(N)
        print(a)
    for b in data_b:  # O(M)
        print(b)
    # Total: O(N + M)

# Loop bersarang → kalikan
def bersarang(data_a, data_b):
    for a in data_a:      # O(N)
        for b in data_b:  # O(M)
            print(a, b)
    # Total: O(N × M)

Contoh Kasus Nyata

Kasus: Mencari Duplikat dalam Array

Solusi Naif — O(N²):

function cariDuplikatLambat(arr) {
  const duplikat = [];
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j] && !duplikat.includes(arr[i])) {
        duplikat.push(arr[i]);
      }
    }
  }
  
  return duplikat;
}

const data = [1, 2, 3, 2, 4, 3, 5];
console.log(cariDuplikatLambat(data)); // [2, 3]

Solusi Optimal — O(N):

function cariDuplikatCepat(arr) {
  const dilihat = new Set();
  const duplikat = new Set();
  
  for (const angka of arr) {       // Satu kali loop: O(N)
    if (dilihat.has(angka)) {      // Set lookup: O(1)
      duplikat.add(angka);
    } else {
      dilihat.add(angka);
    }
  }
  
  return [...duplikat];
}

const data = [1, 2, 3, 2, 4, 3, 5];
console.log(cariDuplikatCepat(data)); // [2, 3]

Dengan menggunakan Set (hash table), kita menurunkan kompleksitas dari O(N²) menjadi O(N) — untuk 10.000 elemen, perbedaannya bisa dari 100 juta operasi menjadi hanya 10.000 operasi!

Kesimpulan

Big O Notation adalah alat berpikir, bukan rumus ajaib. Intinya sederhana: bagaimana performa algoritma kamu berubah ketika datanya bertambah banyak?

Ringkasan cepat dari yang terbaik ke terburuk:

O(1) → O(log N) → O(N) → O(N log N) → O(N²) → O(2^N)
 ↑                                                   ↑
Terbaik                                         Terburuk

Langkah praktis untuk kamu mulai:

1. Hitung loop — setiap loop tambah satu level (N), nested loop kalikan (N²)
2. Abaikan konstanta — O(3N) = O(N)
3. Ambil suku dominan — O(N² + N) = O(N²)
4. Pilih struktur data yang tepat — Set/HashMap sering mengubah O(N) menjadi O(1) untuk pencarian

Tidak perlu langsung hafal semua. Mulai dari kenali O(1), O(N), dan O(N²) terlebih dahulu — tiga kompleksitas itu sudah cukup untuk membuat kamu berpikir lebih kritis saat menulis kode sehari-hari.