Big-O Notation

Pada Chapter sebelumnya kita menghitung operasi dasar secara eksak: 999 perbandingan untuk nilai maksimum, 10 perbandingan untuk pencarian biner. Angka eksak itu ampuh untuk verifikasi, tetapi angka itu berubah setiap kali ukuran input berubah — kita tidak mau menghitung ulang untuk setiap n. Big-O adalah bahasa ringkas untuk menyatakan bagaimana jumlah operasi tumbuh ketika n membesar, tanpa terjebak pada detail konstanta. Chapter ini membahas definisi formal Big-O dalam bentuk paling sederhana, aturan membuang konstanta dan suku rendah, asal-usul logaritma dari binary search, dan cara menganalisis loop bersarang.

Definisi Formal Secara Sederhana #

Pernyataan “f(n) adalah O(g(n))” punya makna matematis yang bisa diverifikasi: ada konstanta positif c dan batas n0 sehingga untuk semua n ≥ n0, nilai f(n) tidak pernah melampaui c · g(n). Tulisan O(g(n)) bukan fungsi, melainkan himpunan batas atas — g(n) menjadi tali pagar yang mengikat laju pertumbuhan f(n) setelah n melewati n0. Konstanta c memberi ruang pengali, dan n0 memberi ruang “permulaan” yang boleh berbeda.

Mari kita buktikan dengan fungsi konkret f(n) = 3n² + 20n + 7 yang kita klaim berada di O(n²) dengan c = 4:

java
DefinisiFormal.java
public class DefinisiFormal {

    public static void main(String[] args) {
        // f(n) = 3n^2 + 20n + 7   ->   g(n) = n^2 dengan konstanta c = 4
        int c = 4;
        int batasAtas = 100_000;

        // Cari n0 terkecil sejak mana f(n) <= c * g(n) mulai berlaku.
        int n0 = -1;
        for (int n = 1; n <= batasAtas; n++) {
            if (f(n) <= c * g(n)) {
                n0 = n;
                break;
            }
        }

        // Pastikan pertidaksamaan tetap berlaku untuk semua n >= n0.
        boolean tetapBerlaku = true;
        for (int n = n0; n <= batasAtas; n++) {
            if (f(n) > c * g(n)) {
                tetapBerlaku = false;
                break;
            }
        }

        System.out.println("f(n) = 3n^2 + 20n + 7   g(n) = n^2   c = " + c);
        System.out.println("n0 terkecil yang memenuhi f(n) <= c*g(n): " + n0);
        System.out.println("Diverifikasi tetap berlaku sampai n=" + batasAtas
                + ": " + (tetapBerlaku ? "ya" : "tidak"));
    }

    static long f(int n) {
        return 3L * n * n + 20L * n + 7;
    }

    static long g(int n) {
        return 1L * n * n;
    }
}

Output yang Dihasilkan:

text
f(n) = 3n^2 + 20n + 7   g(n) = n^2   c = 4
n0 terkecil yang memenuhi f(n) <= c*g(n): 21
Diverifikasi tetap berlaku sampai n=100000: ya

Ternyata untuk n ≥ 21, nilai 3n² + 20n + 7 selalu kurang dari atau sama dengan 4n². Mari kita bedah logika pencariannya:

Baris 10-16 (loop pertama): program mencoba n = 1, 2, 3, … dan berhenti pada n pertama yang memenuhi f(n) ≤ c·g(n). Loop menemukan n0 = 21 karena pada n = 20 nilai 20n + 7 masih sedikit di atas n².
Baris 18-25 (loop kedua): menemukan n0 saja belum cukup — definisi mensyaratkan pertidaksamaan berlaku untuk semua n ≥ n0. Loop kedua memeriksa ulang seluruh rentang sampai 100000 dan hasilnya tetap berlaku.
Baris 33-35 (f dan g): dua fungsi kecil dipisah agar pertidaksamaan terbaca persis seperti rumus matematikanya. Tipe kembalian long menjaga perkalian besar tidak luber di tengah pemeriksaan.

Membuang Konstanta dan Suku Rendah #

Dari definisi di atas lahir dua aturan praktis yang membuat analisis ringkas. Pertama, konstanta pengali dibuang: 3n² dan 900n² sama-sama O(n²) karena c bisa dipilih untuk menyerapnya. Kedua, suku berderajat lebih rendah dibuang: pada 3n² + 20n + 7, suku 20n dan 7 tenggelam ketika n membesar. Program berikut menunjukkan gejala “tenggelam” tersebut dengan angka nyata, sekaligus membandingkan laju loop bersarang lawan binary search:

java
AnalisisBigO.java
public class AnalisisBigO {

    public static void main(String[] args) {
        System.out.println("=== Loop bersarang: n naik 2x, operasi naik 4x ===");
        for (int n = 10; n <= 40; n *= 2) {
            System.out.printf("n=%3d -> %5d iterasi loop dalam%n",
                    n, hitungLoopBersarang(n));
        }

        System.out.println();
        System.out.println("=== Binary search: n naik 4x, perbandingan hanya +2 ===");
        for (int n = 1024; n <= 16384; n *= 4) {
            System.out.printf("n=%5d -> %2d perbandingan (target di ujung kanan)%n",
                    n, hitungBiner(n));
        }

        System.out.println();
        System.out.println("=== Suku rendah tenggelam: f(n) = 3n^2 + 20n + 7 ===");
        for (int n = 10; n <= 10000; n *= 10) {
            long fn = 3L * n * n + 20L * n + 7;
            System.out.printf("n=%5d -> f(n)=%10d, f(n)/n^2 = %.3f%n",
                    n, fn, (double) fn / (1L * n * n));
        }
    }

    static long hitungLoopBersarang(int n) {
        long iterasi = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                iterasi++;
            }
        }
        return iterasi;
    }

    static int hitungBiner(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = i + 1;
        }
        int target = n;          // nilai terbesar: kasus paling kanan
        int lo = 0;
        int hi = n - 1;
        int perbandingan = 0;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            perbandingan++;
            if (a[mid] == target) {
                return perbandingan;
            }
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return perbandingan;
    }
}

Output yang Dihasilkan:

text
=== Loop bersarang: n naik 2x, operasi naik 4x ===
n= 10 ->   100 iterasi loop dalam
n= 20 ->   400 iterasi loop dalam
n= 40 ->  1600 iterasi loop dalam

=== Binary search: n naik 4x, perbandingan hanya +2 ===
n= 1024 -> 11 perbandingan (target di ujung kanan)
n= 4096 -> 13 perbandingan (target di ujung kanan)
n=16384 -> 15 perbandingan (target di ujung kanan)

=== Suku rendah tenggelam: f(n) = 3n^2 + 20n + 7 ===
n=   10 -> f(n)=       507, f(n)/n^2 = 5.070
n=  100 -> f(n)=     32007, f(n)/n^2 = 3.201
n= 1000 -> f(n)=   3020007, f(n)/n^2 = 3.020
n=10000 -> f(n)= 300200007, f(n)/n^2 = 3.002

Tiga pola penting terbaca langsung dari output tersebut. Pertama, rasio f(n)/n² merambat menuju 3.000 — suku 20n dan 7 nyaris tidak berperan lagi pada n = 10000. Kedua, setiap penggandaan n pada loop bersarang melipatempatkan operasi (100 → 400 → 1600). Ketiga, setiap penggandaan input pada binary search hanya menambah satu langkah, sehingga n yang naik 4× (1024 → 4096 → 16384) cukup dibayar 2 perbandingan tambahan (11 → 13 → 15).

Membaca Grafik Pertumbuhan #

Kurva berikut memvisualkan mengapa kelas kompleksitas berbeda begitu dominan. Untuk rentang n = 1 sampai 30, bandingkan jumlah operasi versi O(log n), O(n), O(n log n), dan O(n²):

xychart-beta title "Jumlah operasi untuk n = 1 hingga 30" x-axis "ukuran input n" [1, 5, 10, 15, 20, 25, 30] y-axis "jumlah operasi" 0 --> 900 line "O(log n)" [0, 2, 3, 4, 4, 5, 5] line "O(n)" [1, 5, 10, 15, 20, 25, 30] line "O(n log n)" [0, 12, 33, 59, 86, 116, 147] line "O(n^2)" [1, 25, 100, 225, 400, 625, 900]

Pada n = 30, kurva O(n²) sudah menembus 900 operasi sementara O(log n) masih berkutat pada 5 operasi. Selisih kelas yang tampak kecil pada input mungil melebar drastis pada input besar — inilah alasan memilih algoritma yang tepat jauh lebih berdampak daripada mempercepat konstanta.

Logaritma dari Binary Search #

Dari mana O(log n) muncul? Setiap iterasi binary search memotong rentang pencarian menjadi tepat setengah: 1024 menjadi 512, lalu 256, 128, dan seterusnya hingga tersisa satu elemen. Banyaknya pemotongan sampai habis adalah jumlah kali 1024 harus dibagi dua — itulah log₂(1024) = 10, ditambah satu perbandingan terakhir, sehingga program kita mencatat 11 perbandingan. Benih inilah yang membuat binary search O(log n): input berlipat empat hanya menambah dua langkah, sesuai output AnalisisBigO di atas.

Menganalisis Loop Bersarang #

Aturan analisis loop bisa dirangkum dalam dua kalimat. Loop yang berurutan menghasilkan penjumlahan: tiga loop O(n) berjalan bergiliran tetap O(n). Loop yang bersarang menghasilkan perkalian: loop O(n) di dalam loop O(n) menjadi O(n²), terbukti dari hitungan 100 → 400 → 1600 ketika n digandakan dari 10 → 20 → 40. Saat ada keraguan, pasang penghitung di loop paling dalam seperti method hitungLoopBersarang — angka eksak tidak pernah berbohong.

Dengan kosakata Big-O di tangan, kita siap membedah struktur data pertama yang menyimpan data paling mendasar: array dan linked list, beserta tabel biaya operasinya.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

java
public class AnalisisBigO {

    public static void main(String[] args) {
        System.out.println("=== Loop bersarang: n naik 2x, operasi naik 4x ===");
        for (int n = 10; n <= 40; n *= 2) {
            System.out.printf("n=%3d -> %5d iterasi loop dalam%n",
                    n, hitungLoopBersarang(n));
        }

        System.out.println();
        System.out.println("=== Binary search: n naik 4x, perbandingan hanya +2 ===");
        for (int n = 1024; n <= 16384; n *= 4) {
            System.out.printf("n=%5d -> %2d perbandingan (target di ujung kanan)%n",
                    n, hitungBiner(n));
        }

        System.out.println();
        System.out.println("=== Suku rendah tenggelam: f(n) = 3n^2 + 20n + 7 ===");
        for (int n = 10; n <= 10000; n *= 10) {
            long fn = 3L * n * n + 20L * n + 7;
            System.out.printf("n=%5d -> f(n)=%10d, f(n)/n^2 = %.3f%n",
                    n, fn, (double) fn / (1L * n * n));
        }
    }

    static long hitungLoopBersarang(int n) {
        long iterasi = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                iterasi++;
            }
        }
        return iterasi;
    }

    static int hitungBiner(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = i + 1;
        }
        int target = n;          // nilai terbesar: kasus paling kanan
        int lo = 0;
        int hi = n - 1;
        int perbandingan = 0;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            perbandingan++;
            if (a[mid] == target) {
                return perbandingan;
            }
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return perbandingan;
    }
}

java
public class DefinisiFormal {

    public static void main(String[] args) {
        // f(n) = 3n^2 + 20n + 7   ->   g(n) = n^2 dengan konstanta c = 4
        int c = 4;
        int batasAtas = 100_000;

        // Cari n0 terkecil sejak mana f(n) <= c * g(n) mulai berlaku.
        int n0 = -1;
        for (int n = 1; n <= batasAtas; n++) {
            if (f(n) <= c * g(n)) {
                n0 = n;
                break;
            }
        }

        // Pastikan pertidaksamaan tetap berlaku untuk semua n >= n0.
        boolean tetapBerlaku = true;
        for (int n = n0; n <= batasAtas; n++) {
            if (f(n) > c * g(n)) {
                tetapBerlaku = false;
                break;
            }
        }

        System.out.println("f(n) = 3n^2 + 20n + 7   g(n) = n^2   c = " + c);
        System.out.println("n0 terkecil yang memenuhi f(n) <= c*g(n): " + n0);
        System.out.println("Diverifikasi tetap berlaku sampai n=" + batasAtas
                + ": " + (tetapBerlaku ? "ya" : "tidak"));
    }

    static long f(int n) {
        return 3L * n * n + 20L * n + 7;
    }

    static long g(int n) {
        return 1L * n * n;
    }
}