Time Complexity dan Big-O

Sebuah function yang menghitung total 10 transaksi terasa sekejap — tetapi apakah masih sekejap saat datanya 10 juta? Jawabannya tidak ditentukan kecepatan komputer, melainkan bagaimana waktu eksekusi tumbuh ketika input membesar. Time complexity adalah bahasa untuk menjawab pertanyaan itu, dan notasi Big-O adalah cara menuliskannya. Pada Chapter ini kita pelajari kelas-kelas kompleksitas yang paling sering dijumpai, lalu membuktikan bedanya dengan pengukuran nyata.

Apa Itu Big-O #

Big-O menjawab satu pertanyaan: bila jumlah input dinaikkan, berapa kali lipat waktu eksekusi bertambah? Notasi ini sengaja membuang detail yang tidak berpengaruh pada pola pertumbuhan. O(2n + 5) ditulis O(n) karena konstanta dan suku kecil tidak mengubah bentuk kurva; yang penting apakah waktu naik linear (O(n)), kuadratik (O(n²)), atau tidak naik sama sekali (O(1)).

Lima kelas yang paling sering kita temui sehari-hari:

Tabel Pertumbuhan #

Angka-angka di bawah ini adalah jumlah operasi untuk tiap ukuran input n — cara paling cepat merasakan beda antar kelas:

Bila tabel ini digambar sebagai grafik dengan sumbu horizontal ukuran data dan sumbu vertikal jumlah operasi, kolom O(1) berupa garis datar, O(log n) nyaris menempel ke lantai, O(n) naik lurus, O(n log n) naik lurus dengan sedikit lengkung, dan O(n²) melengkung tajam ke atas seperti dinding — pada n = 10.000, kurva O(n²) sudah 100 juta operasi sementara O(n) baru 10 ribu. Perhatikan pula lompatan dari n = 100 ke n = 10.000 (100x lipat): kolom O(log n) hanya bertambah dari 6,6 ke 13,3 — nyaris dua kali lipat — padahal O(n²) memburuk 10.000 kali lipat.

Membuktikannya dengan Pengukuran Nyata #

O(n) vs O(1): in pada list vs set #

Membership check x in list memindai elemen satu per satu — linear. x in set memakai hash table — konstan. Kita ukur 100 kali pencarian nilai yang tidak ada (kasus terburuk bagi list):

import time

UKURAN = 100_000
data_list = list(range(UKURAN))
data_set = set(range(UKURAN))

target = [UKURAN + i for i in range(100)]  # tidak pernah ditemukan

mulai = time.perf_counter()
for t in target:
    t in data_list
waktu_list = time.perf_counter() - mulai

mulai = time.perf_counter()
for t in target:
    t in data_set
waktu_set = time.perf_counter() - mulai

print(f"100 pencarian di list ({UKURAN:,} elemen): {waktu_list * 1000:.1f} ms")
print(f"100 pencarian di set  ({UKURAN:,} elemen): {waktu_set * 1000:.3f} ms")
print(f"list lebih lambat {waktu_list / waktu_set:,.0f}x")

Output yang Dihasilkan (waktu bergantung pada mesin):

100 pencarian di list (100,000 elemen): 88.8 ms
100 pencarian di set  (100,000 elemen): 0.009 ms
list lebih lambat 9,930x

List menjadi 10.000 kali lebih lambat bukan karena Python lamban, melainkan karena struktur yang berbeda membawa kelas kompleksitas yang berbeda — materi struktur data set sudah kita bahas pada Chapter Set.

O(n log n): Sorting #

Algoritma sorting berbasis perbandingan seperti Timsort (yang dipakai sorted()) berjalan dalam O(n log n). Ciri khasnya terlihat saat data diperbesar 10x — waktunya bertambah sedikit lebih dari 10x, karena suku log n ikut membesar:

import random
import time

random.seed(42)

for ukuran in (100_000, 1_000_000):
    data = [random.randint(0, 10_000_000) for _ in range(ukuran)]
    mulai = time.perf_counter()
    hasil = sorted(data)
    durasi = time.perf_counter() - mulai
    print(f"sorted({ukuran:>9,} data) : {durasi:.3f} detik")

Output yang Dihasilkan (waktu bergantung pada mesin):

sorted(  100,000 data) : 0.017 detik
sorted(1,000,000 data) : 0.252 detik

Data naik 10x, waktu naik sekitar 15x — di antara 10x (kalau O(n)) dan 100x (kalau O(n²)), persis wilayah O(n log n).

O(n²): Dua Loop Bersarang #

Dua for bersarang atas data yang sama menghasilkan n × n iterasi. Ciri keramatnya: setiap penggandaan n melipat empatkan waktu:

import time


def hitung_pasangan(n):
    jumlah = 0
    for i in range(n):
        for j in range(n):
            jumlah += 1
    return jumlah


for n in (1_000, 2_000, 4_000):
    mulai = time.perf_counter()
    hitung_pasangan(n)
    durasi = time.perf_counter() - mulai
    print(f"n = {n:>5,} : {durasi:.4f} detik")

Output yang Dihasilkan (waktu bergantung pada mesin):

n = 1,000 : 0.0359 detik
n = 2,000 : 0.1478 detik
n = 4,000 : 0.5980 detik

Dari n = 1.000 ke 2.000 waktu naik 4,1x; dari 2.000 ke 4.000 tepat 4x — pola kuadratik murni yang mudah dikenali dari pengukuran seperti ini.

Best, Average, dan Worst Case #

Satu algoritma bisa punya beberapa kompleksitas tergantung keberuntungan datanya. Pencarian linear menemukan target pertama dalam satu langkah (best case O(1)) atau memindai semua (worst case O(n)), rata-rata separuh data. Quicksort terkenal O(n log n) rata-rata tetapi jatuh ke O(n²) pada pivot buruk — alasan Timsort lebih dipilih untuk standard library. Konvensi sehari-hari: ketika orang menyebut “complexity dari X”, yang dimaksud biasanya worst case, karena itulah jaminan yang bisa dipegang saat data nyata datang dari luar kendali kita.

Space Complexity dan Biaya Amortized #

Kompleksitas juga berlaku untuk memori — space complexity. Sorting in-place seperti list.sort() hanya O(1) memori tambahan, sedangkan sorted() membuat list baru O(n). Sebaliknya, hash table menukar memori dengan kecepatan: set 100 ribu elemen jauh lebih besar daripada list-nya (ingat sys.getsizeof pada Chapter Memahami Memory Management: set kosong saja 216 byte).

Satu istilah terakhir yang sering muncul di dokumentasi Python: list.append() berlabel O(1) amortized. Sesekali append memicu realokasi yang menyalin seluruh isi list — mahal, O(n) — tetapi karena over-allocation menyediakan slot cadangan, realokasi itu jarang; dibagi rata ke seluruh append, biaya rata-ratanya konstan. Jadi satu append tertentu boleh lambat, namun sejuta append berturut-turut tetap tumbuh linear.