Notasi Big-O adalah bahasa standar untuk menyatakan batas atas pertumbuhan sebuah fungsi. Ketika kita menulis T(n) = O(n log n), kita tidak menyatakan bahwa T(n) sama persis dengan n log n, melainkan bahwa T(n) tidak tumbuh lebih cepat dari n log n untuk n yang cukup besar. Pada Chapter ini kita akan memformalkan definisi Big-O, mempelajari cara membuktikan sebuah fungsi berada dalam kelas Big-O tertentu, dan menerapkan aturan aljabar untuk menyederhanakan ekspresi kompleksitas.

Definisi Formal Big-O #

Misalkan f(n) dan g(n) adalah fungsi yang memetakan bilangan bulat non-negatif ke bilangan real non-negatif. Kita menyatakan bahwa:

f(n) = O(g(n)) jika dan hanya jika terdapat konstanta positif c dan n₀ sehingga 0 ≤ f(n) ≤ c·g(n) untuk semua n ≥ n₀.

Artinya, mulai dari suatu titik n₀, fungsi f(n) tidak pernah melebihi c kali g(n). Konstanta c menyerap faktor-faktor konstan (seperti koefisien atau biaya per operasi), dan n₀ menyerap suku-suku ordo lebih rendah yang hanya dominan untuk n kecil.

Mekanisme: Mengapa Definisi seperti Ini #

Definisi Big-O menggunakan batas atas agar fleksibel: bila f(n) = O(g(n)) dan ternyata g(n) lebih besar dari yang sebenarnya dibutuhkan, hubungan tersebut tetap benar. Misal f(n) = 2n + 5 juga O(n²) secara matematis, tetapi kita biasanya menyatakan O(n) karena itu batas yang ketat (tight). Big-O tidak mengikat kita pada batas ketat; itu tugas Big-Theta yang akan kita pelajari nanti.

Cara Membuktikan f(n) = O(g(n)) #

Untuk membuktikan f(n) = O(g(n)), kita harus menemukan c dan n₀ eksplisit sehingga pertidaksamaan f(n) ≤ c·g(n) dipenuhi untuk semua n ≥ n₀.

Contoh Pembuktian #

Misalkan f(n) = 3n² + 5n + 7. Kita ingin menunjukkan f(n) = O(n²).

Langkah 1: cari batas atas dengan ekspresi sederhana.

Untuk n ≥ 1:

  • 5n ≤ 5n² (karena n ≤ n² untuk n ≥ 1)
  • 7 ≤ 7n² (karena 1 ≤ n² untuk n ≥ 1)
  • 3n² = 3n²

Maka f(n) = 3n² + 5n + 7 ≤ 3n² + 5n² + 7n² = 15n².

Langkah 2: pilih c = 15 dan n₀ = 1. Untuk semua n ≥ 1, 0 ≤ f(n) ≤ 15·n². ∎

Aturan Aljabar Big-O #

Berikut aturan praktis untuk menyederhanakan ekspresi Big-O:

AturanBentuk asalHasil
Konstanta diabaikanO(5n)O(n)
Suku ordo rendah diabaikanO(n² + n + 1)O(n²)
Penjumlahan: ambil maksimumO(n²) + O(n)O(n²)
PerkalianO(n) × O(n)O(n²)
O(log n) < O(n)O(log n + n)O(n)
Komposisi loop bersarangO(n) × O(m)O(n·m)

Kode: Verifikasi Numerik Pembuktian #

cpp 
#include <iostream>
#include <cmath>

// f(n) yang akan kita analisis
long long f(int n) {
    return 3LL * n * n + 5LL * n + 7;
}

// g(n) = 15 * n^2 sebagai batas atas
long long g(int n) {
    return 15LL * n * n;
}

int main() {
    std::cout << "n\tf(n)\tg(n)=15n^2\tf<=g?\n";
    for (int n : {0, 1, 2, 5, 10, 100, 1000}) {
        long long fn = f(n);
        long long gn = g(n);
        std::cout << n << '\t' << fn << '\t' << gn
                  << (fn <= gn ? "\tYA" : "\tTIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
n	f(n)	g(n)=15n^2	f<=g?
0	7	0	TIDAK
1	15	15	YA
2	29	60	YA
5	107	375	YA
10	357	1500	YA
100	30507	150000	YA
1000	3005007	15000000	YA

Bedah Kode Baris-per-Baris #

  1. Fungsi f: menghitung 3n² + 5n + 7 dengan tipe long long untuk menghindari overflow pada n besar.
  2. Fungsi g: batas atas teoritis 15n² sesuai pembuktian kita.
  3. Loop for (int n : {...}): structured binding list menyederhanakan iterasi nilai n yang berbeda.
  4. Baris output: menampilkan n, f(n), g(n), dan hasil pembandingan. Output menunjukkan untuk n=0, f(0) = 7 > g(0) = 0, tetapi mulai n=1, pertidaksamaan terpenuhi. Inilah mengapa definisi Big-O menggunakan n₀: kita hanya peduli pada n yang cukup besar.
  5. Implikasi: konstanta c=15 dan n₀=1 adalah satu pilihan valid. Banyak pilihan lain juga valid; tidak ada keharusan menemukan c minimum.

Hierarki Fungsi Asimptotik #

Berikut pertumbuhan beberapa kelas fungsi umum, diurutkan dari paling lambat tumbuh ke paling cepat:

Fungsin=10n=100n=1.000n=10.000
11111
log₂ n3,36,610,013,3
√n3,210,031,6100,0
n101001.00010.000
n log₂ n336649.966132.877
n²10010.0001.000.000100.000.000
n³1.0001.000.00010⁹10¹²
2ⁿ1.024≈10³⁰≈10³⁰¹≈10³⁰¹⁰
n!≈3,6×10⁶≈9,3×10¹⁵⁷≈4×10²⁵⁶⁷≈2,8×10³⁵⁶⁵⁹

Aturan Praktis Menentukan Big-O #

Saat membaca kode, gunakan aturan praktis berikut untuk menentukan Big-O dengan cepat:

Konstruksi KodeBig-O
Urutan pernyataan O(1)O(1)
if-else dengan kedua cabang O(1)O(1)
Loop tunggal for (i=0; i<n; ++i) berisi O(1)O(n)
Loop bersarang n × nO(n²)
Loop bersarang n × mO(n·m)
Loop dengan i = i * 2 (binary search)O(log n)
Loop dengan i = i * 2 luar + loop n dalamO(n log n)
Rekursi f(n) = f(n-1) + O(1)O(n)
Rekursi f(n) = 2·f(n/2) + O(n)O(n log n)
std::sort(v.begin(), v.end())O(n log n)

Kegunaan dan Keterbatasan Big-O #

Big-O berguna untuk membandingkan algoritma secara asimptotik, tetapi memiliki beberapa keterbatasan yang perlu disadari:

  • Mengabaikan konstanta: O(n) belum tentu lebih cepat dari O(n²) pada n kecil. Misal insertion sort O(n²) sering kali mengalahkan merge sort O(n log n) untuk n < 50 karena konstanta kecil.
  • Hanya menjawab worst case asimptotik: tidak menjelaskan kasus rata-rata atau best case.
  • Tidak memperhitungkan cache: algoritma cache-friendly dengan Big-O sama bisa 10× lebih cepat di praktik.
  • Tidak menjelaskan awal memori: dua fungsi O(1) bisa memiliki jejak memori sangat berbeda.

Ringkasan #

  • f(n) = O(g(n)) berarti f(n) dibatasi atas oleh c·g(n) untuk n ≥ n₀.
  • Pembuktian Big-O dilakukan dengan menemukan c dan n₀ eksplisit.
  • Aturan aljabar: abaikan konstanta, abaikan suku ordo rendah, gunakan penjumlahan dan perkalian.
  • Hierarki pertumbuhan: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!.
  • Big-O adalah batas atas; tidak menjanjikan ketat (tight), sehingga kita perlu Big-Theta untuk pernyataan yang lebih presisi.

Pada Chapter berikutnya kita akan mempelajari Big-Omega — notasi kembar Big-O yang menyatakan batas bawah asimptotik.