Belajar Algoritm - Asymptotic Analysis Lanjut: Omega & Theta, Recurrence Relations

#Pendahuluan

Setelah di episode 1 kita memahami definisi formal algoritma dan korektivitas, pada episode ini kita memperdalam alat analisis yang paling powerful: asymptotic notation dan recurrence relations. Jika Big-O (yang sudah kalian kenal dari episode 0) adalah upper bound, maka ada dua notasi lagi yang melengkapi gambaran: Big-Omega (lower bound) dan Big-Theta (tight bound).

Menguasai notasi ini penting karena algoritma sering dibandingkan secara formal. Ketika seseorang berkata "algoritma ini Θ(n log n)", mereka mengklaim bahwa tidak ada algoritma yang lebih cepat dari itu untuk masalah yang sama — bukan sekadar "cukup cepat".

#Big-Omega (Ω): Lower Bound

Big-Omega memberikan batas bawah pertumbuhan fungsi. Jika f(n) = Ω(g(n)), maka f(n) tumbuh setidaknya secepat g(n) untuk n yang cukup besar.

python

# Fungsi ini minimal melakukan n operasi
def at_least_linear(arr):
    result = 0
    for x in arr:       # minimal n iterasi
        result += x
    return result

at_least_linear adalah Ω(n) — ia minimal melakukan n iterasi, meskipun bisa lebih jika ada operasi tambahan. Omega berguna untuk membuktikan lower bound suatu masalah: "tidak ada algoritma yang bisa menyelesaikan masalah X lebih cepat dari Ω(g(n))".

#Big-Theta (Θ): Tight Bound

Big-Theta adalah tight bound — f(n) = Θ(g(n)) berarti f(n) dibatasi oleh g(n) dari atas dan bawah secara simultan. Ini adalah bentuk paling informatif dari asymptotic analysis.

Notasi	Arti	Kapan Digunakan
O(g(n))	Upper bound	Algoritma tidak lebih lambat dari g(n)
Ω(g(n))	Lower bound	Algoritma tidak lebih cepat dari g(n)
Θ(g(n))	Tight bound	Algoritma tumbuh persis seperti g(n)

Contoh: insertion sort pada input acak adalah Θ(n²) — ia selalu melakukan proporsi n² operasi, tidak lebih dan tidak kurang. Namun pada input yang sudah terurut, ia menjadi Θ(n).

Note

Jika kalian hanya mengklaim O(n²) untuk insertion sort, informasinya tidak lengkap — kalian tidak menyatakan apakah ada kasus yang lebih cepat. Θ(n²) pada input acak memberikan gambaran yang jelas: itu adalah pertumbuhan aktual, bukan sekadar batas atas.

#Recurrence Relations

Banyak algoritma — terutama divide & conquer — didefinisikan secara rekursif. Untuk menganalisis kompleksitasnya, kita perlu menyelesaikan recurrence relation: persamaan yang mendefinisikan fungsi dalam hal fungsi yang sama dengan input lebih kecil.

#Contoh Rekursi

Merge sort memiliki rekursi:

plaintext

T(n) = 2T(n/2) + Θ(n)

Artinya: untuk input ukuran n, merge sort memanggil dirinya sendiri 2 kali untuk input ukuran n/2, ditambah Θ(n) untuk operasi merge.

#Tree Method

Tree method memvisualisasikan rekursi sebagai pohon pemanggilan:

text

            T(n)
          /      \
       T(n/2)   T(n/2)
      /    \    /    \
   T(n/4) T(n/4) T(n/4) T(n/4)
    ...       ...       ...

Setiap level memiliki total kerja Θ(n) (karena jumlah node berlipat dua sementara ukuran per node berkurang dua). Kedalaman pohon = log₂(n). Total kerja = Θ(n) × log₂(n) = Θ(n log n).

#Substitution Method

Substitution method adalah induksi matematika untuk recurrence: tebak bentuk solusi, lalu buktikan dengan induksi.

Contoh: tebak T(n) = Θ(n log n) untuk T(n) = 2T(n/2) + n.

Asumsi: T(k) ≤ c·k·log(k) untuk semua k < n.

plaintext

T(n) = 2T(n/2) + n
      ≤ 2·c·(n/2)·log(n/2) + n
      = c·n·(log(n) - 1) + n
      = c·n·log(n) - c·n + n
      ≤ c·n log(n)    (untuk c ≥ 1)

Solusi terbukti.

#Master Theorem

Master Theorem adalah formula siap pakai untuk rekursi berbentuk:

plaintext

T(n) = aT(n/b) + Θ(n^d)

Di mana a ≥ 1 (jumlah sub-problem), b > 1 (faktor penyusutan), d ≥ 0 (eksponen pekerjaan non-rekursif).

Kasus	Kondisi	Solusi
1	d < log_b(a)	T(n) = Θ(n^(log_b(a)))
2	d = log_b(a)	T(n) = Θ(n^d · log n)
3	d > log_b(a)	T(n) = Θ(n^d)

Contoh penerapan — merge sort: T(n) = 2T(n/2) + Θ(n) → a=2, b=2, d=1. log₂(2) = 1 = d → kasus 2 → T(n) = Θ(n log n).

Binary search: T(n) = T(n/2) + Θ(1) → a=1, b=2, d=0. log₂(1) = 0 = d → kasus 2 → T(n) = Θ(log n).

Tip

Master Theorem hanya berlaku untuk rekursi berbentuk aT(n/b) + Θ(n^d). Untuk rekursi bentuk lain (misal T(n) = T(n-1) + Θ(n)), gunakan tree method atau substitution.

#Praktik: Selesaikan Rekursi

Coba selesaikan rekursi berikut secara manual:

Soal 1: T(n) = 4T(n/2) + Θ(n²)

a=4, b=2, d=2. log₂(4) = 2 = d → kasus 2 → T(n) = Θ(n² log n).

Soal 2: T(n) = 2T(n/4) + Θ(√n)

a=2, b=4, d=0.5. log₄(2) = 0.5 = d → kasus 2 → T(n) = Θ(√n · log n).

Soal 3: T(n) = T(n/3) + Θ(n)

a=1, b=3, d=1. log₃(1) = 0 < 1 = d → kasus 3 → T(n) = Θ(n).

Verifikasi dengan mengukur waktu aktual jika diperlukan — teori dan praktik harus selaras.

#Penutup

Pada episode 2 ini, kalian telah memahami:

Big-Omega (Ω): lower bound — algoritma tidak lebih cepat dari ini.
Big-Theta (Θ): tight bound — pertumbuhan aktual fungsi.
Recurrence relations: tree method, substitution, dan Master Theorem (3 kasus).
Master Theorem mempercepat analisis divide & conquer secara drastis.

Di episode 3 selanjutnya kita akan membahas paradigma desain algoritma — overview brute force, divide & conquer, greedy, dynamic programming, backtracking, dan randomized — serta pola pikir untuk memilih paradigma yang tepat untuk sebuah masalah. Sampai jumpa di episode 3!