Bagaimana Biaya Bertambah

Big O mengukur bagaimana biaya bertambah saat input bertambah. Bukan faktor konstanta — melainkan lajunya. Dua algoritma yang keduanya berjalan dalam 'beberapa milidetik' pada N=100 mungkin berbeda hingga faktor 10.000 pada N=10.000, jika satu berjalan dalam waktu O(N) & yang lain dalam O(N²).

Kelas Kompleksitas Umum

O(1) — Konstan. Biaya yang sama terlepas dari N. Contoh: pencarian tabel hash berdasarkan kunci, akses array berdasarkan indeks, push/pop stack. Menggandakan N tidak mengubah apa pun.

O(log N) — Logaritmik. Setiap langkah membagi dua sisa pekerjaan. Contoh: pencarian biner pada array terurut, kueri spasial BVH di mesin permainan, operasi pohon biner seimbang. Pada N=1.000.000: log₂(1.000.000) ≈ 20 langkah.

O(N) — Linier. Biaya bertambah seiring input. Contoh: pemindaian linier pada daftar, membaca file, menghitung item dalam koleksi. Pada N=10.000: 10.000 operasi.

O(N log N) — Linearitmik. Hampir linier, sedikit lebih buruk. Contoh: merge sort, algoritma jalur-terpendek efisien (Dijkstra dengan heap). Pada N=10.000: ~133.000 operasi.

O(N²) — Kuadratik. Biaya meledak. Contoh: list.contains() dipanggil di dalam loop pada daftar yang sama, bubble sort, perbandingan semua-pasangan naif. Pada N=1.000: 1.000.000 operasi. Pada N=10.000: 100.000.000 operasi.

O(2^N) — Eksponensial. Tidak dapat digunakan pada skala yang berarti. Contoh: kombinatorik brute-force, mencari semua subset. Pada N=30: lebih dari 1.000.000.000 operasi.

Skala yang Membuatnya Terlihat

Perbandingan N=10:
O(N):   10
O(N²):  100
rasio:  10x

N=1.000 perbandingan:
O(N):   1.000
O(N²):  1.000.000
rasio:  1.000x

N=10.000 perbandingan:
O(N):   10.000
O(N²):  100.000.000
rasio:  10.000x

Pada N=10, perbedaannya hampir tidak terlihat. Pada N=10.000, algoritma O(N²) berjalan 10.000 kali lebih lambat. Inilah sebabnya MOAD-0001 tetap tidak terlihat selama puluhan tahun: grafik yang dijalankannya pada tahun 1993 hanya memiliki 50 simpul. Pada tahun 2020, kode yang sama berjalan pada grafik dependensi dengan 50.000 simpul.

Klasifikasikan Tiga Operasi

Terapkan kelas kompleksitas pada operasi konkret. Pertanyaan kunci untuk setiap operasi: berapa banyak operasi yang diperlukan saat N bertambah?

Kode Benar, Kurva Pertumbuhan Salah

Kode yang benar yang berjalan dalam waktu O(N²) menghasilkan hasil yang sama persis dengan kode O(N). Tes lulus. Output cocok. Tidak ada pengecualian yang muncul. Cacatnya tersembunyi dalam kurva pertumbuhan.

Sifat ini membuat cacat O(N²) bersifat sedimen: mereka mengeras di dalam kode yang berfungsi & hanya terlihat ketika N tumbuh melewati ambang batas. Kodenya tidak berubah. Dunia di sekitarnya yang berubah.

MOAD-0001: Cacat Sedimen

Contoh paling umum: visited = [] di dalam loop traversal graf.

visited = []
for node in graph:
if node not in visited:  # pemindaian O(N) setiap panggilan
visited.append(node)
process(node)

Setiap pemanggilan not in visited memindai 0 hingga len(visited)-1 item. N pemanggilan × rata-rata N/2 item yang dipindai = total O(N²). Solusinya: satu baris.

visited = set()  # Uji keanggotaan O(1)
for node in graph:
if node not in visited:  # Pencarian hash O(1)
visited.add(node)
process(node)

Perilaku yang sama. Output yang sama. Tes yang sama lolos. Tingkat pertumbuhan berubah dari O(N²) menjadi O(N). Pada N=1.000: 1.000× lebih cepat. Pada N=10.000: 10.000× lebih cepat.

Mengapa Era Hamming Menyebabkan Ini

Di awal Java & C, ArrayList (dynamic array) adalah kontainer sekuensial default. Set memang ada, tetapi tidak idiomatik — pengembang memilih yang sudah familiar. Traversal graf tahun 1993 pada N=50 berjalan dalam mikrodetik dengan visited = []. Kode itu masuk ke version control, disalin, dibungkus dalam library, dan dikirimkan melalui package manager. Pada 2020, pola yang sama berjalan pada dependency graph dengan 50.000 node.

Kodenya benar pada 1993. Menjadi mahal ketika dunia di sekitarnya berubah. Era Hamming menanamkan kelas cacat ini karena tidak pernah menamai pertanyaan tingkat pertumbuhan.

Diagnosis & Perbaikan

Terapkan diagnosis: temukan pola O(N²), identifikasi perbaikannya.

Perubahan Penamaan Apa

Sebelum Big O memiliki nama, programmer menyadari 'ini berjalan lambat.' Mereka melakukan profiling. Mereka menulis ulang. Namun mereka tidak dapat mengajarkan pola tersebut — mereka hanya bisa menunjuk pada contoh-contoh. Pola tanpa nama tidak dapat menyebar.

Setelah Big O memiliki nama, seorang insinyur senior dapat mengatakan 'ini adalah O(N²), ganti dengan set' & seorang insinyur junior dapat memahami, menerapkan, & mengajarkan pola tersebut secara bergantian. Nama tersebut menjadikan pola sebagai unit pengetahuan yang dapat ditransfer.

Hamming mengetahui dinamika ini di domain lain. Ia menjelaskan bagaimana penamaan 'spaghetti code' pada tahun 1960-an memungkinkan komunitas untuk mengenali, mendiskusikan, & akhirnya memberantas kelas cacat yang telah dialami semua orang tetapi belum pernah diberi nama. Mekanisme yang sama berlaku untuk kelas kompleksitas.

Unhamming menambahkan kosakata yang Hamming lewatkan: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Nama-nama ini memungkinkan Anda melihat kurva pertumbuhan dalam kode yang Anda baca, memprediksi performa pada skala besar, & mengomunikasikan perbaikan secara tepat. Mereka memenuhi uji Hamming sendiri untuk sesuatu yang fundamental: tahan lama, & menghasilkan sebagian besar bidang lainnya. [TITLE who_coined_big_o/]

Dari Teori Bilangan ke Ilmu Komputer

Notasi Big O tidak berasal dari ilmu komputer. Ia berasal dari matematika murni — khususnya teori bilangan — 74 tahun sebelum Donald Knuth mengadaptasinya untuk algoritma.

Paul Bachmann, 1894

Paul Bachmann, seorang matematikawan Jerman, memperkenalkan notasi O dalam bukunya tahun 1894 yang berjudul Die Analytische Zahlentheorie (Teori Bilangan Analitik). Ia membutuhkan cara ringkas untuk menyatakan bahwa suatu besaran tidak bertambah lebih cepat daripada besaran lain, hingga faktor konstan. Menulis 'f(n) = O(g(n))' berarti: f bertambah paling lambat secepat g. Hal ini memungkinkan para ahli teori bilangan untuk menalar tentang suku-suku galat dalam aproksimasi tanpa melacak konstanta yang tepat.

Bachmann tidak memikirkan tentang loop, struktur data, atau waktu eksekusi. Ia memikirkan bagaimana bilangan prima terdistribusi — khususnya tentang suku-suku galat dalam Teorema Bilangan Prima.

Edmund Landau, 1909

Edmund Landau, seorang matematikawan Jerman lainnya, mempopulerkan notasi ini dalam bukunya tahun 1909 yang berjudul Handbuch der Lehre von der Verteilung der Primzahlen (Buku Pegangan tentang Distribusi Bilangan Prima). Landau juga memperkenalkan notasi terkait o (little-o) dan menggunakan keluarga simbol asimtotik ini secara luas sehingga keluarga tersebut dikenal sebagai notasi Bachmann-Landau atau sekadar notasi Landau.

Selama enam dekade, notasi O sepenuhnya hidup dalam dunia matematika. Tidak ada programmer yang memikirkannya.

Donald Knuth, 1968 & 1976

Donald Knuth menerjemahkan notasi ini ke dalam ilmu komputer. Dalam The Art of Computer Programming (Vol. 1, 1968), Knuth menggunakan notasi O untuk menggambarkan waktu eksekusi algoritma — sebuah pemindahan langsung alat Bachmann ke domain baru. Ia adalah orang pertama yang menerapkannya secara sistematis pada analisis algoritma.

Pada 1976, Knuth menerbitkan makalah singkat di SIGACT News berjudul 'Big Omicron and Big Omega and Big Theta.' Ia memperkenalkan Omega (Omega) untuk batas bawah dan Theta untuk batas ketat, melengkapi kosakata tiga simbol yang digunakan ilmu komputer saat ini. Ia juga berargumen untuk menstandarkan penggunaan simbol-simbol ini di seluruh bidang — sebuah tindakan standarisasi yang disengaja yang mempercepat adopsi.

Pada awal 1980-an, Big O muncul di setiap buku teks algoritma. Pada 1990-an, ia menjadi kosakata standar dalam wawancara.

Perjalanan 74 Tahun

1894 — Bachmann memperkenalkan O dalam teori bilangan
1909 — Landau mempopulerkan O, o, dan seluruh keluarga notasi
1953 — Hamming memulai penelitian di Bell Labs (tidak pernah mempelajari Big O sebagai alat CS)
1968 — Knuth menerapkan O untuk analisis algoritma dalam TAOCP Vol. 1
1976 — Knuth menambahkan Omega dan Theta; berargumen untuk standarisasi
1980-an — Big O masuk ke semua kurikulum CS
1993 — Lapisan sedimen MOAD-0001 terbentuk dalam kode produksi
1995 — Hamming mengajar versi terakhir kursusnya; tidak pernah membahas Big O
2026 — MOAD-0001 ditemukan di lebih dari 1.000 proyek open-source

Alat Bachmann menghabiskan 74 tahun dalam matematika murni, terlihat oleh setiap matematikawan tetapi tidak terlihat oleh setiap programmer. Knuth melihat potensi transplantasinya. Hamming — yang bekerja di era yang sama dan berkolaborasi dengan komunitas komputasi yang sama — tidak pernah menjadikannya bagian dari kursusnya.

Mengapa Standardisasi Knuth Penting

Makalah Knuth tahun 1976 melakukan lebih dari sekadar memperkenalkan Omega dan Theta. Makalah itu berargumen bahwa bidang ini membutuhkan notasi yang konsisten, dan bahwa notasi yang tidak konsisten justru merugikan. Buku teks yang berbeda menggunakan O dengan makna yang berbeda — terkadang sebagai batas atas, terkadang sebagai pendekatan, terkadang tanpa menjelaskan apakah konstanta diperhitungkan. Knuth membersihkan semua ini.

Ini adalah dinamika penamaan pola Hamming yang diterapkan pada notasi itu sendiri. Sebelum Knuth menstandarisasi simbol-simbol tersebut, para insinyur tidak dapat mengomunikasikan klaim kompleksitas secara tepat di seluruh buku teks, makalah, atau tim. Setelah standardisasi, 'ini berjalan dalam O(N log N)' membawa makna yang persis sama, siapa pun yang mengatakannya.

Knuth juga memberikan terjemahan informal: 'O(f(n)) berarti waktu berjalan paling banyak sebesar konstanta dikalikan f(n), untuk semua n yang cukup besar.' Interpretasi ini — batas atas, hingga faktor konstanta, untuk masukan besar — menjadi intuisi standar yang dipelajari setiap programmer.