Notasi Big-Theta

Bila kita telah mengetahui bahwa f(n) = O(n²) dan juga f(n) = Ω(n²), kita sebenarnya sudah memegang jawaban yang lebih kuat: f(n) tumbuh tepat seperti n² secara asimptotik. Inilah yang dinyatakan oleh notasi Big-Theta. Pada Chapter ini kita akan memformalkan Big-Theta sebagai gabungan Big-O dan Big-Omega, melihat kapan Big-Theta bisa diterapkan, dan membedakan pernyataan “ada batas atas” dari “inilah batas yang ketat”.

Definisi Formal Big-Theta #

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

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

Dengan kata lain, f(n) dijepit oleh dua kelipatan g(n). Inilah pernyataan paling informatif tentang pertumbuhan f(n): tidak hanya ada batas atas, tetapi juga ada batas bawah yang setara.

Hubungan dengan Big-O dan Big-Omega #

Big-Theta adalah gabungan Big-O dan Big-Omega:

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

Membuktikan Big-Theta #

Untuk membuktikan f(n) = Θ(g(n)), kita harus menunjukkan dua hal:

1. f(n) = O(g(n)) — cari c₂ dan n₀ sehingga f(n) ≤ c₂·g(n).
2. f(n) = Ω(g(n)) — cari c₁ dan n₀ sehingga f(n) ≥ c₁·g(n).

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

Bukti Big-O (dari Chapter Notasi Big-O): pilih c₂ = 15 dan n₀ = 1. Untuk n ≥ 1, 3n² + 5n + 7 ≤ 15n². ✓

Bukti Big-Omega (dari Chapter Notasi Big-Omega): pilih c₁ = 3 dan n₀ = 1. Untuk n ≥ 1, 3n² + 5n + 7 ≥ 3n². ✓

Karena keduanya berlaku, f(n) = Θ(n²). ∎

Kode: Verifikasi Eksperimen Big-Theta #

#include <iostream>

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

int main() {
    std::cout << "n\tf(n)\t3n^2\t15n^2\tdalam [3n^2, 15n^2]?\n";
    for (int n : {1, 5, 10, 100, 1000, 10000}) {
        long long fn = f(n);
        long long lb = 3LL * n * n;
        long long ub = 15LL * n * n;
        bool dalam = (lb <= fn && fn <= ub);
        std::cout << n << '\t' << fn << '\t' << lb << '\t' << ub
                  << (dalam ? "\tYA" : "\tTIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

n	f(n)	3n^2	15n^2	dalam [3n^2, 15n^2]?
1	15	3	15	YA
5	107	75	375	YA
10	357	300	1500	YA
100	30507	30000	150000	YA
1000	3005007	3000000	15000000	YA
10000	300050007	300000000	1500000000	YA

Bedah Kode Baris-per-Baris #

1. Fungsi f: polinomial 3n² + 5n + 7 yang ingin kita karakterisasi.
2. Konstanta c₁ = 3, c₂ = 15: dipilih sesuai pembuktian Big-Omega (batas bawah) dan Big-O (batas atas) di Chapter sebelumnya.
3. Baris bool dalam = (lb <= fn && fn <= ub);: memeriksa apakah f(n) berada dalam interval [3n², 15n²]. Jika ya, ini bukti numerik (bukan bukti formal) bahwa f(n) = Θ(n²).
4. Output: untuk semua n ≥ 1, f(n) selalu berada dalam interval. Inilah inti dari Big-Theta: terdapat konstanta c₁ dan c₂ yang menjepit f(n) dalam kelipatan g(n).
5. Catatan: verifikasi numerik bukan pengganti pembuktian formal. Verifikasi hanya memberi keyakinan, bukan kepastian matematis. Pembuktian formal mengikat untuk seluruh n, bukan hanya nilai yang diuji.

Perbedaan Pernyataan Big-O vs Big-Theta #

Banyak pemula menyatakan T(n) = O(n²) padahal yang dimaksud adalah T(n) = Θ(n²). Keduanya berbeda secara teknis:

Cara Praktis Menemukan Big-Theta #

Untuk sebagian besar fungsi yang kita temui di DSA, Big-Theta dapat ditentukan dengan aturan praktis berikut:

1. Identifikasi suku dominan (pangkat tertinggi, atau fungsi asimptotik terbesar).
2. Abaikan koefisien dan suku ordo lebih rendah.
3. Hasilnya adalah Θ(suku dominan).

Membandingkan Big-Theta pada Algoritma #

Berikut beberapa algoritma dengan Big-Theta yang sudah terbukti ketat:

Perhatikan bahwa beberapa algoritma memiliki kompleksitas berbeda antara kasus terbaik dan terburuk (misal insertion sort, quick sort). Inilah mengapa kita perlu berhati-hati saat menyatakan Big-Theta tanpa menyebut kasus.

Kode: Membandingkan Tiga Notasi pada Insertion Sort #

Mekanisme Insertion Sort #

Insertion sort mengambil setiap elemen dan menyisipkannya pada posisi yang tepat di antara elemen-elemen sebelumnya yang sudah terurut. Pada array yang sudah terurut, hanya satu pembandingan per elemen diperlukan (best case Θ(n)). Pada array terurut terbalik, setiap elemen baru harus dibandingkan dengan semua elemen sebelumnya, menghasilkan n(n-1)/2 pembandingan (worst case Θ(n²)).

Kode Program #

#include <iostream>
#include <vector>

long long pembandingan = 0;

void insertionSort(std::vector<int>& v) {
    pembandingan = 0;
    for (std::size_t i = 1; i < v.size(); ++i) {
        int key = v[i];
        int j = static_cast<int>(i) - 1;
        while (j >= 0) {
            ++pembandingan;
            if (v[j] > key) {
                v[j + 1] = v[j];
                --j;
            } else {
                break;
            }
        }
        v[j + 1] = key;
    }
}

int main() {
    std::vector<int> terurut   = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> terbalik  = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    insertionSort(terurut);
    std::cout << "Best case (terurut)    : " << pembandingan << " pembandingan\n";

    insertionSort(terbalik);
    std::cout << "Worst case (terbalik)  : " << pembandingan << " pembandingan\n";
    return 0;
}

Output yang Dihasilkan:

Best case (terurut)    : 9 pembandingan
Worst case (terbalik)  : 45 pembandingan

Bedah Kode Baris-per-Baris #

1. Baris for (std::size_t i = 1; ...): insertion sort mulai dari indeks kedua; elemen pertama dianggap sudah terurut.
2. Baris int key = v[i];: elemen yang akan disisipkan disimpan ke variabel sementara key.
3. Baris while (j >= 0) dan ++pembandingan;: kita menghitung satu pembandingan per iterasi while, termasuk iterasi yang berakhir karena v[j] <= key. Inilah sumber perbedaan best dan worst case.
4. Baris v[j + 1] = v[j]; --j;: menggeser elemen yang lebih besar dari key ke kanan, lalu melanjutkan ke elemen sebelumnya.
5. Best case n = 10: array sudah terurut, sehingga setiap elemen hanya memerlukan satu pembandingan. Total: 9 = n - 1, sesuai Θ(n).
6. Worst case n = 10: array terurut terbalik, sehingga elemen ke-i memerlukan i pembandingan. Total: 1 + 2 + ... + 9 = 45, sesuai Θ(n²) dengan koefisien 1/2.

Ringkasan #

• f(n) = Θ(g(n)) berarti c₁·g(n) ≤ f(n) ≤ c₂·g(n) untuk n ≥ n₀.
• Big-Theta adalah gabungan Big-O dan Big-Omega: keduanya harus berlaku.
• Big-Theta memberi pernyataan paling informatif tentang pertumbuhan fungsi.
• Konvensi DSA sering memakai Big-O untuk menyatakan kompleksitas ketat, meski secara teknis Big-Theta lebih tepat.
• Aturan praktis: ambil suku dominan, abaikan koefisien dan suku ordo rendah.

Pada Chapter berikutnya kita akan mempelajari analisis loop secara sistematis — bagaimana menghitung kompleksitas berbagai pola loop, dari loop tunggal hingga loop bersarang dan loop dengan pertambahan non-trivial.