Kenapa penting

Kode yang terasa cepat saat dites dengan 10 data bisa membuat endpoint timeout saat menghadapi 100.000 data di production. Penyebabnya sering bukan "Java lambat", tetapi algoritma yang tumbuh terlalu cepat — misalnya loop bersarang yang tanpa sadar membandingkan setiap data dengan semua data lain. Notasi Big-O adalah bahasa bersama developer untuk membicarakan bagaimana waktu (dan memori) bertambah ketika data bertambah. Ini juga topik wajib di interview backend, dan alat berpikir untuk memilih struktur data yang tepat dari semua yang sudah kamu pelajari di modul ini.

Konsep inti

Intuisi Big-O

Big-O tidak mengukur detik, tetapi laju pertumbuhan jumlah langkah terhadap ukuran input n. Konstanta dan suku kecil diabaikan: 3n + 5 tetap O(n), karena saat n sangat besar yang menentukan adalah bentuk pertumbuhannya.

Notasi	Nama	Contoh
O(1)	konstan	list.get(i), map.get(key) (rata-rata)
O(log n)	logaritmik	mencari di data terurut dengan membagi dua (binary search), TreeMap.get
O(n)	linear	satu loop atas semua data, list.contains(x)
O(n log n)	linearitmik	mengurutkan (List.sort)
O(n²)	kuadratik	loop bersarang yang membandingkan semua pasangan

Perbedaannya terasa sangat besar saat n membesar. Perkiraan jumlah langkah:

n	log n	n	n log n	n²
10	3	10	33	100
1.000	10	1.000	9.966	1.000.000
1.000.000	20	1.000.000	19.931.569	1.000.000.000.000

Satu juta data dengan algoritma O(n²) berarti satu triliun langkah — berjam-jam. Dengan O(n log n), sekitar 20 juta langkah — sepersekian detik.

Dari mana O(log n) berasal

O(log n) muncul saat setiap langkah membuang separuh sisa data, seperti mencari kata di kamus dengan membuka bagian tengah lalu memilih separuh kiri atau kanan. Berapa kali sebuah angka bisa dibagi dua sampai tersisa 1?

public class HalvingSteps {
    // Berapa kali n bisa dibagi dua sampai tersisa 1? Itulah "log2 n".
    static int steps(long n) {
        int count = 0;
        while (n > 1) {
            n = n / 2;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        long[] sizes = {1_000, 1_000_000, 1_000_000_000};
        for (long n : sizes) {
            System.out.println("n = " + n + " → " + steps(n) + " langkah");
        }
    }
}

Output:

n = 1000 → 9 langkah
n = 1000000 → 19 langkah
n = 1000000000 → 29 langkah

Pembagian bilangan bulat membulatkan ke bawah, jadi hasilnya sedikit di bawah log₂ n (≈ 10, 20, 30). Data seribu kali lebih besar hanya menambah sekitar 10 langkah. Inilah alasan TreeMap (pohon seimbang) dan pencarian pada data terurut tetap cepat walau datanya jutaan.

Kompleksitas operasi collection

Struktur	Akses/cari	Tambah	Hapus
ArrayList	get(i) O(1), contains O(n)	di akhir O(1)*, di tengah O(n)	di tengah O(n)
LinkedList	get(i) O(n), contains O(n)	di ujung O(1)	di ujung O(1)
HashSet	contains O(1) rata-rata	O(1) rata-rata	O(1) rata-rata
HashMap	get/containsKey O(1) rata-rata	put O(1) rata-rata	O(1) rata-rata
TreeMap/TreeSet	O(log n)	O(log n)	O(log n)
ArrayDeque	ujung O(1), contains O(n)	di ujung O(1)*	di ujung O(1)
PriorityQueue	peek O(1), contains O(n)	offer O(log n)	poll O(log n)

* amortized. ArrayList menyimpan elemen di array. Saat penuh, ia membuat array sekitar 1,5 kali lebih besar dan menyalin isinya — operasi O(n), tetapi jarang. Jika biayanya dirata-rata ke semua add, setiap add tetap O(1).

"Rata-rata" pada struktur hash penting: bila banyak kunci jatuh ke laci yang sama — misalnya karena hashCode yang buruk (ingat bab equals & hashCode) — operasinya memburuk. Sejak Java 8, laci yang terlalu penuh di HashMap diubah menjadi pohon, sehingga kasus terburuknya O(log n), bukan O(n), untuk kunci yang bisa dibandingkan.

Mengubah O(n²) menjadi O(n)

Pola paling umum di kode backend: "untuk setiap X, cari pasangannya di daftar Y". Bila Y berupa List, setiap pencarian O(m), dan totalnya O(n × m). Dengan memasukkan Y ke HashSet atau HashMap sekali, setiap pencarian menjadi O(1) dan totalnya O(n + m). Contoh mencocokkan pesanan dengan pembayaran:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class MatchPayments {
    // O(n × m): untuk setiap pesanan, telusuri seluruh daftar pembayaran
    static List<String> unpaidSlow(List<String> orderIds, List<String> paidOrderIds) {
        List<String> unpaid = new ArrayList<>();
        for (String orderId : orderIds) {
            if (!paidOrderIds.contains(orderId)) {     // List.contains = O(m)
                unpaid.add(orderId);
            }
        }
        return unpaid;
    }

    // O(n + m): bangun Set sekali, lalu setiap pengecekan O(1) rata-rata
    static List<String> unpaidFast(List<String> orderIds, List<String> paidOrderIds) {
        Set<String> paid = new HashSet<>(paidOrderIds);
        List<String> unpaid = new ArrayList<>();
        for (String orderId : orderIds) {
            if (!paid.contains(orderId)) {
                unpaid.add(orderId);
            }
        }
        return unpaid;
    }

    public static void main(String[] args) {
        int n = 50_000;
        List<String> orders = new ArrayList<>();
        List<String> payments = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            orders.add("INV-" + i);
            if (i % 10 != 0) {               // 1 dari 10 pesanan belum dibayar
                payments.add("INV-" + i);
            }
        }

        long start = System.nanoTime();
        int slowCount = unpaidSlow(orders, payments).size();
        long slowMs = (System.nanoTime() - start) / 1_000_000;

        start = System.nanoTime();
        int fastCount = unpaidFast(orders, payments).size();
        long fastMs = (System.nanoTime() - start) / 1_000_000;

        System.out.println("Lambat: " + slowCount + " belum dibayar, " + slowMs + " ms");
        System.out.println("Cepat : " + fastCount + " belum dibayar, " + fastMs + " ms");
    }
}

Contoh output (angka milidetik berbeda di setiap mesin dan setiap kali dijalankan):

Lambat: 5000 belum dibayar, 5672 ms
Cepat : 5000 belum dibayar, 9 ms

Hasilnya sama, tetapi versi HashSet ratusan kali lebih cepat — dan selisihnya makin lebar saat data bertambah. Harganya adalah memori tambahan untuk set: trade-off ruang vs waktu yang hampir selalu layak di backend.

Mengukur dengan benar

System.nanoTime() cukup untuk perbandingan kasar seperti di atas, tetapi angka tunggal mudah menipu:

• JVM menjalankan kode dalam mode interpretasi dulu, lalu JIT compiler mengoptimasi kode yang sering dipanggil (warm-up). Pengukuran pertama biasanya lebih lambat.
• Garbage collector, proses lain, dan cache CPU membuat hasil bervariasi antar-run.
• Untuk benchmark serius, gunakan JMH (Java Microbenchmark Harness), yang menangani warm-up, pengulangan, dan statistik.

Lebih penting dari angka adalah bentuk pertumbuhan: jalankan dengan n dan 2n. Bila waktunya kira-kira empat kali lipat, algoritmanya kuadratik.

Kapan Big-O tidak (terlalu) penting

• n kecil. Mencari di List berisi 10 status pesanan tidak perlu HashSet; kode yang paling jelas lebih baik.
• I/O mendominasi. Satu query database atau panggilan HTTP butuh milidetik — jutaan kali lebih lama dari operasi collection di memori. Endpoint yang menjalankan satu query per item (masalah N+1, dibahas di level Spring Boot) lebih lambat daripada loop O(n²) atas 100 elemen di memori.
• Konstanta tetap ada. Dua algoritma O(n) bisa berbeda 10× kecepatannya. Big-O memberi tahu skala, bukan segalanya.

Urutan berpikir yang sehat: tulis kode yang jelas, ukur di tempat yang lambat, lalu perbaiki algoritma atau jumlah I/O yang terbukti menjadi masalah.

Contoh di dunia backend

Saat memilih struktur data, ajukan pertanyaan berdasarkan operasi yang paling sering dilakukan:

// Potongan: memilih struktur data berdasarkan operasi yang dominan
Map<String, Product> productBySku = new HashMap<>();       // cari produk per SKU: O(1) rata-rata
Set<String> processedWebhookIds = new HashSet<>();         // "sudah pernah diproses?": O(1) rata-rata
TreeMap<Long, String> priceIndex = new TreeMap<>();        // rentang harga, terurut: O(log n)
Deque<String> recentRequests = new ArrayDeque<>();         // N request terakhir: O(1) di ujung
PriorityQueue<Job> retryQueue = new PriorityQueue<>();     // job berikutnya menurut prioritas: O(log n)
List<OrderLine> lines = new ArrayList<>();                 // urutan baris pesanan, akses indeks: O(1)

Pertanyaan yang sering muncul	Pilihan
"Cari berdasarkan ID/kunci"	HashMap
"Apakah X sudah ada?" / buang duplikat	HashSet
"Data terurut / cari rentang (min–max)"	TreeMap / TreeSet
"Yang paling penting/terkecil berikutnya"	PriorityQueue
"Antrean FIFO / stack / N terakhir"	ArrayDeque
"Daftar berurutan, sering dibaca per indeks"	ArrayList

Di code review, temuan klasik adalah list.contains(...) atau list.indexOf(...) di dalam loop atas list lain. Bila kedua list bisa berisi ribuan elemen, ubah salah satunya menjadi Set atau Map lebih dulu — persis pola yang kamu latih di DuplicateFinder.

Pertanyaan interview

1. Berapa kompleksitas HashMap.get, dan kapan bisa memburuk?

Rata-rata O(1): hash kunci menentukan laci, lalu equals membandingkan sedikit elemen di laci itu. Bisa memburuk bila banyak kunci bertabrakan hash (misalnya hashCode yang buruk). Sejak Java 8, laci yang padat diubah menjadi pohon sehingga kasus terburuknya O(log n) untuk kunci yang Comparable; tanpa itu, O(n).

2. Bagaimana kamu menemukan duplikat di array berisi sejuta angka secara efisien?

Telusuri sekali sambil memasukkan setiap nilai ke HashSet; bila add mengembalikan false, nilai itu duplikat. Waktu O(n), memori O(n). Alternatif tanpa memori tambahan: urutkan dulu (O(n log n)) lalu bandingkan elemen bersebelahan. Loop bersarang O(n²) tidak layak untuk sejuta data.

3. Apa arti O(1) amortized pada ArrayList.add?

Sebagian besar add hanya menulis ke slot kosong (O(1)). Sesekali array penuh dan harus disalin ke array yang lebih besar (O(n)), tetapi karena kapasitas tumbuh berlipat, penyalinan itu jarang. Bila total biaya dibagi ke semua add, rata-ratanya konstan per elemen.

Jebakan umum

• contains/indexOf pada List di dalam loop → O(n²) tersembunyi. Ubah salah satu ke HashSet/HashMap.
• Memakai LinkedList karena "sisip cepat" padahal kode sering memanggil get(i) — setiap get menelusuri node.
• Menyimpulkan dari satu pengukuran nanoTime. Ada warm-up JIT dan variasi antar-run; bandingkan pertumbuhan n vs 2n, atau pakai JMH.
• Mengoptimasi algoritma di memori padahal bottleneck-nya query database atau HTTP. Ukur dulu.
• Mengabaikan memori. Struktur tambahan mempercepat waktu tetapi memakan RAM; untuk data sangat besar, pertimbangkan pemrosesan bertahap.

Ringkasan

• Big-O menggambarkan laju pertumbuhan langkah terhadap ukuran input; konstanta diabaikan.
• Urutan dari yang paling skalabel: O(1) → O(log n) → O(n) → O(n log n) → O(n²).
• HashMap/HashSet O(1) rata-rata, TreeMap/TreeSet O(log n), List.contains O(n), sort O(n log n).
• Pola "cari pasangan di list lain" diubah dari O(n × m) menjadi O(n + m) dengan HashSet/HashMap — menukar memori dengan waktu.
• Ukur dengan hati-hati (warm-up JIT, JMH untuk benchmark serius); di backend, jumlah I/O sering lebih menentukan.

Bacaan lanjutan

• dev.java — Choosing Immutable Types for Your Key
• Java SE 25 API — HashMap
• OpenJDK — JMH (Java Microbenchmark Harness)