Belajar Data Structure - Analisis Kompleksitas (Big-O, Omega, Theta)

#Pendahuluan

Setelah di episode 1 kita memahami mengapa data structure itu penting dan melihat perbandingan nyata antara hash map vs linear scan, pada episode ini kita mempelajari alat ukur formal untuk membandingkan performa algoritma: Big-O, Big-Omega, dan Big-Theta. Tanpa pemahaman ini, kalian hanya bisa menebak-nebak algoritma mana yang lebih cepat — dan tebakan yang salah di production system bisa berakibat fatal.

Big-O bukan hanya untuk interview teknis. Ia adalah kerangka berpikir yang membantu kalian membuat keputusan berbasis data, bukan intuisi. Ketika kalian menghadapi dua implementasi yang tampak mirip, pemahaman kompleksitas akan memberi tahu kalian mana yang skalabel dan mana yang tidak.

#Notasi Kompleksitas

#Big-O (Upper Bound)

Big-O menggambarkan upper bound — batas atas waktu atau ruang yang dibutuhkan algoritma dalam kondisi terburuk. Ini adalah notasi yang paling sering digunakan dalam diskusi sehari-hari karena memberikan jaminan performa minimum.

Ketika kalian membaca "algoritma ini O(n)", itu berarti waktu eksekusi tidak akan pernah melebihi konstanta tertentu kali n. Pada praktiknya, Big-O adalah what matters — ia menjawab pertanyaan "seberapa buruk kondisi terburuknya?"

#Big-Omega (Lower Bound)

Big-Omega menggambarkan lower bound — batas bawah waktu atau ruang. Ia menjawab pertanyaan "sebaik apa kondisi terbaiknya?". Misalnya, binary search adalah Omega(1) karena bisa langsung menemukan elemen di posisi tengah pada kondisi terbaik.

#Big-Theta (Tight Bound)

Big-Theta menggambarkan tight bound — batas yang ketat, di mana upper dan lower bound adalah pertumbuhan yang sama. Ketika algoritma adalah Theta(n), itu berarti waktu eksekusi selalu berkembang proporsional dengan n, tidak lebih dan tidak kurang.

#Best, Worst, Average Case

Ketiga notasi di atas berhubungan dengan tiga skenario eksekusi:

• Best case: input paling menguntungkan (misal: elemen yang dicari ada di posisi pertama)
• Worst case: input paling merugikan (misal: elemen yang dicari ada di posisi terakhir atau tidak ada)
• Average case: rata-rata di semua kemungkinan input

Big-O biasanya merujuk pada worst case karena memberikan jaminan yang paling kuat.

#Teknik Analisis

#Drop Constants

Konstanta diabaikan dalam notasi Big-O karena yang penting adalah pertumbuhan relatif seiring bertambahnya input, bukan nilai absolutnya. Algoritma yang butuh 2n langkah dan n langkah keduanya adalah O(n) — karena pada skala besar, faktor 2 tidak relevan.

#Drop Lower Terms

Suku yang lebih rendah juga diabaikan. Jika algoritma butuh n^2 + n langkah, itu ditulis O(n^2) — karena pada n yang besar, n^2 jauh lebih dominan dari n.

#Analisis Loop

Untuk loop sederhana yang iterasi n kali dengan kerja konstan di dalamnya, kompleksitasnya O(n). Untuk nested loop yang masing-masing iterasi n kali, kompleksitasnya O(n^2).

#Analisis Rekursi

Rekursi lebih kompleks. Rekursi sederhana seperti faktorial yang memanggil diri sendiri n kali dengan kerja konstan per panggilan menghasilkan O(n). Binary search yang membagi input dua di setiap langkah menghasilkan O(log n).

#Lima Contoh Analisis

Kita akan menganalisis lima fungsi secara manual, lalu mengukur waktunya secara empiris di Python:

Lima fungsi dengan kompleksitas berbeda

import time
 
def linear_scan(arr, target):
    for item in arr:
        if item == target:
            return True
    return False
 
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False
 
def nested_loop(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count
 
def simple_recursive(n):
    if n <= 0:
        return 0
    return n + simple_recursive(n - 1)
 
def hash_lookup(hash_map, key):
    return hash_map.get(key)

#Analisis Manual

Sebelum menjalankan kode, coba analisis manual:

• linear_scan: dalam kondisi terburuk (elemen tidak ada), kita memeriksa semua n elemen → O(n)
• binary_search: setiap langkah membagi search space menjadi dua → O(log n)
• nested_loop: loop luar n kali, loop dalam n kali → n × n = O(n^2)
• simple_recursive: n panggilan rekursif, masing-masing O(1) → O(n)
• hash_lookup: hash function langsung mengarah ke index → O(1)

#Uji Empiris

Jalankan pengukuran waktu untuk memverifikasi analisis manual:

Uji empiris lima fungsi

import time
 
n_values = [1000, 5000, 10000, 50000]
 
for n in n_values:
    arr = list(range(n))
    target = n - 1
 
    start = time.perf_counter()
    linear_scan(arr, target)
    linear_t = time.perf_counter() - start
 
    start = time.perf_counter()
    binary_search(sorted(arr), target)
    binary_t = time.perf_counter() - start
 
    start = time.perf_counter()
    nested_loop(1000)
    nested_t = time.perf_counter() - start
 
    print(f"n={n:>6}: linear={linear_t:.4f}s  binary={binary_t:.6f}s")

Perhatikan bahwa linear scan berbanding lurus dengan n, binary search tumbuh jauh lebih lambat, dan nested loop sangat lambat bahkan untuk n yang relatif kecil.

#Penutup

Inti yang harus dibawa pulang:

• Big-O = upper bound (terburuk), Big-Omega = lower bound (terbaik), Big-Theta = tight bound (tepat).
• Drop constants dan lower terms — yang penting adalah pertumbuhan relatif.
• Linear scan O(n), binary search O(log n), nested loop O(n^2), recursive O(n), hash lookup O(1).
• Selalu verifikasi analisis manual dengan uji empiris.

Di episode 3 selanjutnya kita akan membahas array dan string — contiguous memory, O(1) random access, dynamic array dengan amortized append O(1), immutability string, serta pattern penting seperti sliding window dan two-pointer. Pastikan kalian sudah paham Big-O karena kita akan menggunakannya untuk menganalisis setiap operasi di episode selanjutnya!