Master Theorem

Master Theorem adalah formula siap pakai untuk menyelesaikan recurrence berbentuk T(n) = a · T(n/b) + f(n) — bentuk yang menutupi sebagian besar algoritma divide and conquer. Daripada melakukan substitusi atau recursion tree dari awal setiap kali, Master Theorem memberi jawaban langsung berdasarkan tiga kasus. Pada Chapter ini kita akan mempelajari ketiga kasus, kapan masing-masing berlaku, dan menerapkannya pada algoritma klasik seperti merge sort, binary search, dan Strassen matrix multiplication.

Pernyataan Master Theorem #

Misalkan a ≥ 1 dan b > 1 adalah konstanta, dan f(n) fungsi non-negatif. Recurrence:

text

T(n) = a · T(n / b) + f(n)

memiliki solusi sebagai berikut, tergantung relasi antara f(n) dan n^(log_b a):

Kasus	Kondisi	Solusi
Kasus 1	`f(n) = O(n^(log_b a - ε))` untuk suatu `ε > 0`	`T(n) = Θ(n^(log_b a))`
Kasus 2	`f(n) = Θ(n^(log_b a))`	`T(n) = Θ(n^(log_b a) · log n)`
Kasus 3	`f(n) = Ω(n^(log_b a + ε))` untuk suatu `ε > 0`, dan `a · f(n/b) ≤ k · f(n)` untuk `k < 1` dan `n` besar	`T(n) = Θ(f(n))`

dengan log_b a adalah logaritma a berbasis b.

flowchart TD A["T n = a·T n/b + f n"] --> B{"Bandingkan f n dengan n^(log_b a)"} B -- "f lebih kecil" --> C["Kasus 1: T = Θ(n^(log_b a))"] B -- "f sama besar" --> D["Kasus 2: T = Θ(n^(log_b a) log n)"] B -- "f lebih besar" --> E["Kasus 3: T = Θ(f n)"]

Cara Mengingat Tiga Kasus #

Intuisi Master Theorem: ada pertarungan antara dua kontribusi biaya:

Biaya leaves — n^(log_b a) yang berasal dari a^log_b n = n^(log_b a) leaf pada recursion tree.
Biaya internal nodes — f(n) yang berasal dari biaya combine/divide per level.

Pemenang pertarungan menentukan kasus:

Bila leaves mendominasi: Kasus 1 — T(n) = Θ(n^(log_b a)).
Bila keduanya seimbang: Kasus 2 — T(n) = Θ(n^(log_b a) · log n) (ada log n level, masing-masing berkontribusi n^(log_b a)).
Bila internal mendominasi: Kasus 3 — T(n) = Θ(f(n)).

Contoh 1: Merge Sort (Kasus 2) #

Recurrence: T(n) = 2T(n/2) + O(n).

Identifikasi Parameter #

a = 2, b = 2, f(n) = Θ(n).
log_b a = log₂ 2 = 1.
n^(log_b a) = n¹ = n.
f(n) = Θ(n) = Θ(n^(log_b a)). Kasus 2 berlaku.

Solusi #

text

T(n) = Θ(n^(log_b a) · log n) = Θ(n log n).

Kode: Verifikasi Numerik Merge Sort #

cpp
#include <iostream>

long long T(long long n) {
    if (n <= 1) return 0;
    return 2 * T(n / 2) + n;
}

int main() {
    for (long long n : {16, 32, 64, 128, 1024}) {
        std::cout << "n=" << n << "\tT(n)=" << T(n)
                  << "\tn log n=" << n * 10
                  << "\tratio=" << static_cast<double>(T(n)) / (n * 10)
                  << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
n=16    T(n)=64 n log n=160     ratio=0.4
n=32    T(n)=160        n log n=320     ratio=0.5
n=64    T(n)=384        n log n=640     ratio=0.6
n=128   T(n)=896        n log n=1280    ratio=0.7
n=1024  T(n)=10240      n log n=10240   ratio=1

Bedah Kode Baris-per-Baris #

Fungsi T(n): implementasi langsung dari recurrence T(n) = 2T(n/2) + n dengan T(1) = 0 (base case).
Baris 2 * T(n / 2) + n: dua pemanggilan rekursif berukuran n/2 ditambah biaya n untuk combine.
Output: rasio T(n) / (n · log₂ n) konvergen ke 1 saat n membesar. Untuk n = 1024, rasio tepat 1, sesuai prediksi T(n) = Θ(n log n).
Implikasi: walau untuk n kecil rasio < 1 karena base case T(1) = 0, konvergensi ke 1 menunjukkan koefisien leading tepat 1 — artinya T(n) = n log₂ n + O(n) secara presisi.

Contoh 2: Binary Search (Kasus 2) #

Recurrence: T(n) = T(n/2) + O(1).

Identifikasi Parameter #

a = 1, b = 2, f(n) = Θ(1).
log_b a = log₂ 1 = 0.
n^(log_b a) = n⁰ = 1.
f(n) = Θ(1) = Θ(n^(log_b a)). Kasus 2 berlaku.

Solusi #

text

T(n) = Θ(n^0 · log n) = Θ(log n).

Contoh 3: Strassen Matrix Multiplication (Kasus 1) #

Recurrence: T(n) = 7T(n/2) + O(n²).

Identifikasi Parameter #

a = 7, b = 2, f(n) = Θ(n²).
log_b a = log₂ 7 ≈ 2,807.
n^(log_b a) = n^2.807.
f(n) = Θ(n²) vs n^(log_b a) = Θ(n^2.807). Karena 2 < 2,807, f(n) = O(n^(log_b a - ε)) dengan ε ≈ 0,807. Kasus 1 berlaku.

Solusi #

text

T(n) = Θ(n^(log_b a)) = Θ(n^2.807).

Kode: Verifikasi Numerik Strassen #

cpp
#include <iostream>
#include <cmath>

long long T(long long n) {
    if (n <= 1) return 1;
    return 7 * T(n / 2) + n * n;
}

int main() {
    for (long long n : {2, 4, 8, 16, 32}) {
        long long tn = T(n);
        double exponent = std::log2(7);    // log_2 7
        double teoritis = std::pow(n, exponent);
        std::cout << "n=" << n << "\tT(n)=" << tn
                  << "\tn^log2(7)=" << teoritis
                  << "\tratio=" << tn / teoritis
                  << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
n=2     T(n)=11 n^log2(7)=7     ratio=1.57143
n=4     T(n)=93 n^log2(7)=49    ratio=1.89796
n=8     T(n)=715        n^log2(7)=343   ratio=2.08455
n=16    T(n)=5261       n^log2(7)=2401  ratio=2.19117
n=32    T(n)=37851      n^log2(7)=16807 ratio=2.2521

Bedah Kode Baris-per-Baris #

Fungsi T(n): implementasi recurrence T(n) = 7T(n/2) + n² dengan T(1) = 1 (base case).
Baris 7 * T(n / 2) + n * n: tujuh pemanggilan rekursif berukuran n/2 ditambah biaya combine n².
Baris double exponent = std::log2(7);: menghitung log₂ 7 ≈ 2,807 sebagai konstanta floating-point.
Output: rasio T(n) / n^log2(7) tumbuh dari 1,57 hingga sekitar 2,25 lalu menstabil. Pola ini konsisten dengan leading term c · n^log2(7) dengan c yang menstabil pada sekitar 2,25. Untuk n lebih besar, rasio akan konvergen ke nilai tetap (sekitar 2,3-2,4). Pola asimptotik Θ(n^2.807) tetap benar.
Implikasi: walaupun rasio belum stabil untuk n kecil, pola asimptotik jelas menunjukkan T(n) = Θ(n^2.807). Strassen mengalahkan perkalian matriks naive O(n³) untuk n cukup besar (biasanya n ≥ 100).

Contoh 4: Kasus 3 — `T(n) = 3T(n/2) + n²` #

Mari kita lihat contoh Kasus 3 secara artifisial.

Identifikasi Parameter #

a = 3, b = 2, f(n) = Θ(n²).
log_b a = log₂ 3 ≈ 1,585.
n^(log_b a) = n^1.585.
f(n) = Θ(n²) vs n^1.585. Karena 2 > 1,585, f(n) = Ω(n^(log_b a + ε)) dengan ε ≈ 0,415.

Pemeriksaan Regularity Condition #

Kasus 3 juga memerlukan a · f(n/b) ≤ k · f(n) untuk k < 1:

text

a · f(n/b) = 3 · (n/2)² = 3n²/4 = 0.75 · n²

Jadi a · f(n/b) = 0.75 · f(n) dengan k = 0.75 < 1. Kondisi terpenuhi. Kasus 3 berlaku.

Solusi #

text

T(n) = Θ(f(n)) = Θ(n²).

Tabel Ringkasan Master Theorem #

Recurrence	a	b	log_b a	f(n)	Kasus	Solusi
`T(n) = 2T(n/2) + n`	2	2	1	n	2	`Θ(n log n)`
`T(n) = T(n/2) + 1`	1	2	0	1	2	`Θ(log n)`
`T(n) = 4T(n/2) + n²`	4	2	2	n²	2	`Θ(n² log n)`
`T(n) = 4T(n/2) + n`	4	2	2	n	1	`Θ(n²)`
`T(n) = 4T(n/2) + n³`	4	2	2	n³	3	`Θ(n³)`
`T(n) = 7T(n/2) + n²`	7	2	~2,807	n²	1	`Θ(n^2.807)`
`T(n) = 3T(n/2) + n²`	3	2	~1,585	n²	3	`Θ(n²)`
`T(n) = 8T(n/2) + n²`	8	2	3	n²	1	`Θ(n³)`
`T(n) = 2T(n/2) + n log n`	2	2	1	n log n	(extended)	`Θ(n log² n)`
`T(n) = 2T(n/2) + 1`	2	2	1	1	1	`Θ(n)`

Keterbatasan Master Theorem #

Master Theorem tidak dapat menyelesaikan beberapa recurrence:

f(n) bukan polinomial: misal T(n) = 2T(n/2) + n/log n. Antara Kasus 2 dan Kasus 3 (gap).
a atau b tidak konstanta: misal T(n) = T(√n) + 1 (bukan T(n/b)).
Recurrence linier: T(n) = T(n-1) + n tidak berbentuk T(n/b).
Regularitas gagal: a · f(n/b) > k · f(n) untuk semua k < 1. Jarang terjadi, tetapi mungkin.

Pada kasus-kasus ini, gunakan substitution method atau recursion tree.

Kode: Membandingkan Tiga Kasus #

cpp
#include <iostream>
#include <cmath>

// Kasus 1: T(n) = 4T(n/2) + n  -> Θ(n^2)
long long kasus1(long long n) {
    if (n <= 1) return 1;
    return 4 * kasus1(n / 2) + n;
}

// Kasus 2: T(n) = 4T(n/2) + n^2  -> Θ(n^2 log n)
long long kasus2(long long n) {
    if (n <= 1) return 1;
    return 4 * kasus2(n / 2) + n * n;
}

// Kasus 3: T(n) = 4T(n/2) + n^3  -> Θ(n^3)
long long kasus3(long long n) {
    if (n <= 1) return 1;
    return 4 * kasus3(n / 2) + n * n * n;
}

int main() {
    long long n = 32;
    std::cout << "n = " << n << '\n';
    std::cout << "Kasus 1 (T = 4T n/2 + n):     " << kasus1(n)
              << " | n^2 = " << n * n << '\n';
    std::cout << "Kasus 2 (T = 4T n/2 + n^2):   " << kasus2(n)
              << " | n^2 log n = " << n * n * 5 << '\n';
    std::cout << "Kasus 3 (T = 4T n/2 + n^3):   " << kasus3(n)
              << " | n^3 = " << n * n * n << '\n';
    return 0;
}

Output yang Dihasilkan:

text
n = 32
Kasus 1 (T = 4T n/2 + n):     2016 | n^2 = 1024
Kasus 2 (T = 4T n/2 + n^2):   6144 | n^2 log n = 5120
Kasus 3 (T = 4T n/2 + n^3):   64512 | n^3 = 32768

Bedah Kode Baris-per-Baris #

Fungsi kasus1: implementasi T(n) = 4T(n/2) + n. Dengan a = 4, b = 2, log_b a = 2. Karena f(n) = n = O(n^(2-ε)) dengan ε = 1, Kasus 1 berlaku, solusi Θ(n²). Output 2016 ≈ 2 × n² = 2048, konsisten dengan leading term n² plus konstanta tambahan.
Fungsi kasus2: implementasi T(n) = 4T(n/2) + n². Karena f(n) = n² = Θ(n^(log_b a)), Kasus 2 berlaku, solusi Θ(n² log n). Output 6144 vs n² log n = 5120 (rasio 1,2), konsisten dengan log₂ n = 5 level.
Fungsi kasus3: implementasi T(n) = 4T(n/2) + n³. Karena f(n) = n³ = Ω(n^(2+ε)) dengan ε = 1 dan regularity terpenuhi, Kasus 3 berlaku, solusi Θ(n³). Output 64512 ≈ 2 × n³ = 65536, konsisten dengan leading term n³.
Implikasi: ketiga kasus Master Theorem memberi prediksi yang berbeda — Kasus 1 didominasi leaf, Kasus 2 seimbang, Kasus 3 didominasi root. Memilih kasus yang tepat menentukan solusi yang benar.

Ringkasan #

Master Theorem menyelesaikan T(n) = a · T(n/b) + f(n) dalam tiga kasus berdasarkan relasi f(n) dengan n^(log_b a).
Kasus 1: f(n) lebih kecil → T(n) = Θ(n^(log_b a)).
Kasus 2: f(n) seimbang → T(n) = Θ(n^(log_b a) · log n).
Kasus 3: f(n) lebih besar (dengan regularity) → T(n) = Θ(f(n)).
Contoh klasik: merge sort (Kasus 2, O(n log n)), binary search (Kasus 2, O(log n)), Strassen (Kasus 1, O(n^2.807)).
Master Theorem terbatas pada recurrence standar; untuk kasus khusus gunakan substitution atau recursion tree.

Dengan berakhirnya Section 5, kita telah memiliki perangkat lengkap untuk membicarakan kompleksitas dan kebenaran algoritma. Pada Section berikutnya, array-dan-matriks, kita akan mulai menerapkan perangkat ini pada struktur data konkret.

Pernyataan Master Theorem #

Cara Mengingat Tiga Kasus #

Contoh 1: Merge Sort (Kasus 2) #

Identifikasi Parameter #

Solusi #

Kode: Verifikasi Numerik Merge Sort #

Bedah Kode Baris-per-Baris #

Contoh 2: Binary Search (Kasus 2) #

Identifikasi Parameter #

Solusi #

Contoh 3: Strassen Matrix Multiplication (Kasus 1) #

Identifikasi Parameter #

Solusi #

Kode: Verifikasi Numerik Strassen #

Bedah Kode Baris-per-Baris #

Contoh 4: Kasus 3 — T(n) = 3T(n/2) + n² #

Identifikasi Parameter #

Pemeriksaan Regularity Condition #

Solusi #

Tabel Ringkasan Master Theorem #

Keterbatasan Master Theorem #

Kode: Membandingkan Tiga Kasus #

Bedah Kode Baris-per-Baris #

Ringkasan #

Contoh 4: Kasus 3 — `T(n) = 3T(n/2) + n²` #