Big-O memberikan batas atas pertumbuhan fungsi, tetapi tidak menjawab pertanyaan: “Apakah algoritma ini paling tidak sekalian cepat ini?”. Notasi Big-Omega melengkapi Big-O dengan menyatakan batas bawah asimptotik. Bersama Big-O, keduanya membentuk sepasang batas yang membingkai perilaku fungsi. Pada Chapter ini kita akan memformalkan definisi Big-Omega, membedakannya dari Big-O, dan memahami kapan batas bawah menjadi pertanyaan yang menarik.

Definisi Formal Big-Omega #

Misalkan f(n) dan g(n) adalah fungsi non-negatif. Kita menyatakan:

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

Artinya, mulai dari n₀, fungsi f(n) tidak pernah kurang dari c kali g(n). Big-Omega menjawab pertanyaan “Apakah f(n) tumbuh sekurang-kurangnya secepat g(n)?”.

Hubungan dengan Big-O #

Big-Omega adalah kebalikan Big-O. Hubungan ini dinyatakan dengan kesetaraan berikut:

f(n) = O(g(n)) jika dan hanya jika g(n) = Ω(f(n)).

Jika f dibatasi atas oleh g, maka g otomatis menjadi batas bawah bagi f. Sebagai contoh, karena 3n + 5 = O(n²), maka n² = Ω(3n + 5).

Kapan Big-Omega Menjadi Pertanyaan Menarik #

Big-O biasanya lebih mudah ditentukan daripada Big-Omega: untuk menunjukkan f = O(g), kita cukup menemukan satu batas atas yang berlaku. Untuk Big-Omega, kita harus menunjukkan bahwa f tidak bisa lebih lambat dari g. Big-Omega menjadi penting ketika kita ingin berbicara tentang:

  • Lower bound masalah: “Berapa operasi minimum yang diperlukan algoritma mana pun untuk menyelesaikan masalah ini?” Misalnya, sorting berbasis pembandingan memiliki lower bound Ω(n log n).
  • Best case complexity: berapa operasi minimum yang dilakukan algoritma pada input terbaik.
  • Analisis algoritma online: pada algoritma dengan input yang datang bertahap, kita sering tertarik pada batas bawah kinerja.

Membuktikan Big-Omega #

Contoh: f(n) = 3n² + 5n + 7 adalah Ω(n²) #

Langkah 1: cari batas bawah yang sederhana.

Untuk n ≥ 1:

  • 3n² = 3n² (suku utama)
  • 5n + 7 ≥ 0 (selalu benar untuk n ≥ 0)

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

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

Kode: Verifikasi Numerik Big-Omega #

cpp 
#include <iostream>

long long f(int n) {
    return 3LL * n * n + 5LL * n + 7;
}

long long lowerBound(int n) {
    return 3LL * n * n;       // c * g(n)
}

int main() {
    std::cout << "n\tf(n)\t3n^2\tf>=3n^2?\n";
    for (int n : {0, 1, 2, 5, 10, 100, 1000}) {
        long long fn = f(n);
        long long lb = lowerBound(n);
        std::cout << n << '\t' << fn << '\t' << lb
                  << (fn >= lb ? "\tYA" : "\tTIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
n	f(n)	3n^2	f>=3n^2?
0	7	0	YA
1	15	3	YA
2	29	12	YA
5	107	75	YA
10	357	300	YA
100	30507	30000	YA
1000	3005007	3000000	YA

Bedah Kode Baris-per-Baris #

  1. Fungsi f: menghitung 3n² + 5n + 7. Suku dominan 3n² akan menjadi batas bawah teoritis.
  2. Fungsi lowerBound: ekspresi 3·n² yang menjadi c·g(n). Kita memilih c = 3 karena koefisien suku utama adalah 3.
  3. Loop iterasi n: kita menguji beberapa nilai untuk memverifikasi pertidaksamaan secara empiris.
  4. Baris output: untuk n = 0, f(0) = 7 ≥ 0 (lower bound terpenuhi). Untuk seluruh n ≥ 0, f(n) ≥ 3n². Implikasinya: f(n) = Ω(n²).
  5. Kontras dengan Big-O: pada Chapter Big-O, kita memilih c = 15 dan n₀ = 1 sehingga f(n) ≤ 15n². Sekarang kita memilih c = 3 dan n₀ = 0 (atau n₀ = 1) sehingga f(n) ≥ 3n². Kombinasi keduanya menunjukkan bahwa f(n) terjepit antara 3n² dan 15n².

Tabel Perbandingan Big-O, Big-Omega, Big-Theta #

NotasiArtiPertidaksamaan
f(n) = O(g(n))Batas atasf(n) ≤ c·g(n) untuk n ≥ n₀
f(n) = Ω(g(n))Batas bawahf(n) ≥ c·g(n) untuk n ≥ n₀
f(n) = Θ(g(n))Batas ketatc₁·g(n) ≤ f(n) ≤ c₂·g(n)

Big-Omega untuk Lower Bound Masalah #

Berbeda dengan lower bound algoritma tertentu, lower bound masalah berbicara tentang berapa minimum operasi yang diperlukan algoritma mana pun untuk menyelesaikan masalah tersebut.

MasalahLower BoundCatatan
Mencari maksimum n elemenΩ(n)Harus memeriksa setiap elemen sekurang-kurangnya satu kali
Sorting berbasis pembandinganΩ(n log n)Berlaku untuk semua algoritma yang membandingkan pasangan elemen
Pencarian pada array tak terurutΩ(n)Tidak ada cara lain selain memeriksa satu per satu
Pencarian pada array terurutΩ(log n)Setiap pembandingan membagi ruang pencarian paling banyak 2
Perkalian matriks n×nΩ(n²)Harus menyentuh setiap elemen
Median dari arrayΩ(n)Setiap algoritma deterministik perlu membaca seluruh input

Contoh: Lower Bound pada Pencarian Maksimum #

Mari kita bahas mengapa mencari maksimum pada array tak terurut memerlukan sekurang-kurangnya n - 1 pembandingan, sehingga time complexity-nya Ω(n).

Mekanisme Argumen Adversary #

Bayangkan algoritma yang mencoba menemukan maksimum dengan k pembandingan. Setiap elemen yang belum pernah “kalah” dalam pembandingan masih mungkin menjadi maksimum, sehingga algoritma tidak bisa memutuskan dengan keyakinan. Pada awalnya, n elemen adalah “kandidat maksimum”. Setiap pembandingan maksimal mengeliminasi satu kandidat. Untuk menyisakan tepat satu kandidat, diperlukan tepat n - 1 eliminasi, yaitu n - 1 pembandingan.

Kode: Verifikasi Eksperimen #

cpp 
#include <iostream>
#include <vector>
#include <algorithm>

int cariMaks(const std::vector<int>& v, long long& cmp) {
    cmp = 0;
    int maks = v[0];
    for (std::size_t i = 1; i < v.size(); ++i) {
        ++cmp;                  // satu pembandingan
        if (v[i] > maks) maks = v[i];
    }
    return maks;
}

int main() {
    for (int n : {10, 100, 1000, 10000}) {
        std::vector<int> data(n);
        for (int i = 0; i < n; ++i) data[i] = i;
        long long cmp = 0;
        cariMaks(data, cmp);
        std::cout << "n=" << n
                  << " | pembandingan=" << cmp
                  << " | n-1=" << (n - 1)
                  << " | sama? " << (cmp == n - 1 ? "YA" : "TIDAK")
                  << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
n=10 | pembandingan=9 | n-1=9 | sama? YA
n=100 | pembandingan=99 | n-1=99 | sama? YA
n=1000 | pembandingan=999 | n-1=999 | sama? YA
n=10000 | pembandingan=9999 | n-1=9999 | sama? YA

Bedah Kode Baris-per-Baris #

  1. Baris int maks = v[0];: elemen pertama dijadikan kandidat awal. Pada titik ini kita sudah melakukan 0 pembandingan, dan n - 1 elemen lain masih kandidat.
  2. Baris for (std::size_t i = 1; ...): iterasi dimulai dari indeks 1, sehingga elemen v[0] tidak dihitung ulang.
  3. Baris ++cmp; if (v[i] > maks) ...: setiap pembandingan maksimal mengeliminasi satu kandidat (yaitu v[i] jika kalah, atau maks sebelumnya jika kalah).
  4. Output: untuk n = 10, algoritma melakukan tepat 9 = n - 1 pembandingan. Pola ini berulang untuk semua n, sesuai dengan lower bound teoritis Ω(n - 1) = Ω(n).
  5. Implikasi: algoritma linear scan ini sudah optimal dalam hal jumlah pembandingan. Tidak ada algoritma lain yang bisa menemukan maksimum pada array tak terurut dengan kurang dari n - 1 pembandingan.

Ringkasan #

  • f(n) = Ω(g(n)) berarti f(n) dibatasi bawah oleh c·g(n) untuk n ≥ n₀.
  • Big-Omega adalah kebalikan Big-O: f = O(g) ⟺ g = Ω(f).
  • Big-Omega berguna untuk berbicara tentang lower bound masalah dan best case complexity.
  • Sorting berbasis pembandingan memiliki lower bound Ω(n log n); pencarian pada array tak terurut Ω(n); pencarian pada array terurut Ω(log n).
  • Pencarian maksimum membutuhkan tepat n - 1 pembandingan, sehingga Ω(n) dan optimal.

Pada Chapter berikutnya kita akan mempelajari Big-Theta, notasi yang menggabungkan Big-O dan Big-Omega menjadi satu pernyataan ketat tentang pertumbuhan fungsi.