Setiap algoritma rekursif memiliki recurrence relation yang menggambarkan biaya T(n) dalam bentuk T pada input lebih kecil. Membaca dan menyelesaikan recurrence relation adalah keterampilan dasar untuk menganalisis algoritma divide and conquer, sorting, dan struktur data berbasis rekursi. Pada Chapter ini kita akan belajar menurunkan recurrence dari kode rekursif, menyelesaikannya dengan substitution method dan recursion tree, serta mempersiapkan diri untuk Master Theorem di Chapter berikutnya.

Apa itu Recurrence Relation #

Recurrence relation adalah persamaan yang mendefinisikan fungsi berdasarkan dirinya sendiri pada argumen lebih kecil, dengan satu atau lebih base case. Bentuk umum untuk analisis algoritma:

text 
T(n) = a · T(n / b) + f(n)        (divide and conquer)
T(n) = T(n - 1) + f(n)            (rekursi linier)
T(n) = T(n - 1) + T(n - 2) + f(n) (rekursi bercabang)

dengan:

  • a — jumlah sub-masalah rekursif.
  • b — faktor pembagian ukuran sub-masalah.
  • f(n) — biaya non-rekursif (divide, combine, base case).

Pola 1: Rekursi Linier — Faktorial #

cpp 
long long factorial(int n) {
    if (n <= 1) return 1;     // base case: T(1) = O(1)
    return n * factorial(n - 1);  // recursive case
}

Recurrence: T(n) = T(n-1) + O(1), dengan T(1) = O(1).

cpp 
int binarySearch(const std::vector<int>& v, int lo, int hi, int target) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (v[mid] == target) return mid;
    else if (v[mid] < target) return binarySearch(v, mid + 1, hi, target);
    else return binarySearch(v, lo, mid - 1, target);
}

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

Pola 3: Merge Sort #

cpp 
void mergeSort(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(v, lo, mid);       // T(n/2)
    mergeSort(v, mid + 1, hi);   // T(n/2)
    merge(v, lo, mid, hi);       // O(n) — combine
}

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

Pola 4: Karatsuba Multiplication #

cpp 
BigInteger karatsuba(BigInteger x, BigInteger y) {
    if (x < 10 || y < 10) return x * y;   // base case
    int n = max(digits(x), digits(y));
    int m = n / 2;
    auto [high1, low1] = split(x, m);
    auto [high2, low2] = split(y, m);
    auto z0 = karatsuba(low1, low2);
    auto z1 = karatsuba(low1 + high1, low2 + high2);
    auto z2 = karatsuba(high1, high2);
    return (z2 << (2 * m)) + ((z1 - z2 - z0) << m) + z0;
}

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

Tabel Recurrence dan Solusi #

RecurrenceSolusiContoh Algoritma
T(n) = T(n-1) + O(1)O(n)Linear search rekursif, faktorial
T(n) = T(n-1) + O(n)O(n²)Quick sort worst, selection sort rekursif
T(n) = T(n-1) + T(n-2) + O(1)O(φⁿ) ≈ O(1,618ⁿ)Fibonacci naif
T(n) = 2T(n-1) + O(1)O(2ⁿ)Tower of Hanoi
T(n) = T(n/2) + O(1)O(log n)Binary search
T(n) = T(n/2) + O(n)O(n)Pencarian linear scan + rekursi paruh
T(n) = 2T(n/2) + O(1)O(n)Traversal tree seimbang
T(n) = 2T(n/2) + O(n)O(n log n)Merge sort
T(n) = 2T(n/2) + O(log n)O(n)(kasus khusus)
T(n) = 3T(n/2) + O(n)O(n^log₂3) ≈ O(n^1.585)Karatsuba
T(n) = 7T(n/2) + O(n²)O(n^log₂7) ≈ O(n^2.807)Strassen
T(n) = 4T(n/2) + O(n²)O(n²)(kasus khusus Master Theorem)

Metode 1: Substitution Method #

Substitution method adalah teknik menebak solusi lalu membuktikannya dengan induksi matematis.

Contoh: T(n) = 2T(n/2) + n #

Tebakan: T(n) = O(n log n).

Pembuktian: Asumsikan T(k) ≤ c · k log k untuk semua k < n. Maka:

text 
T(n) = 2T(n/2) + n
     ≤ 2 · c · (n/2) · log(n/2) + n
     = c · n · (log n - 1) + n
     = c · n log n - c · n + n
     = c · n log n - (c - 1) · n
     ≤ c · n log n            (asalkan c ≥ 1)

Dengan c ≥ 1 dan n₀ cukup besar, pertidaksamaan terpenuhi. Maka T(n) = O(n log n). ∎

Metode 2: Recursion Tree #

Recursion tree memvisualisasikan pemanggilan rekursif sebagai pohon. Setiap node menampilkan biaya f(n) pada pemanggilan tersebut, dan anak-anaknya menampilkan sub-masalah.

Cara Menghitung Total Biaya #

  1. Biaya per level: pada level k terdapat 2^k node, masing-masing berbiaya n/2^k. Total per level: 2^k × n/2^k = n.
  2. Jumlah level: pohon berhenti saat n/2^k = 1, yaitu k = log₂ n. Jadi terdapat log₂ n + 1 level (termasuk root).
  3. Biaya total: n × (log n + 1) = Θ(n log n).

Kode: Visualisasi Recursion Tree #

cpp 
#include <iostream>

int main() {
    int n = 16;
    long long biayaPerLevel[20] = {0};
    int maxLevel = 0;

    // Simulasi: pada level k, ada 2^k node, masing-masing berbiaya n / 2^k
    for (int k = 0; (n >> k) >= 1; ++k) {
        int nodeCount = 1 << k;             // 2^k
        int sizePerNode = n >> k;            // n / 2^k
        biayaPerLevel[k] = 1LL * nodeCount * sizePerNode;
        maxLevel = k + 1;
    }

    long long total = 0;
    std::cout << "Level\tNode\tSize/Node\tBiaya\n";
    for (int k = 0; k < maxLevel; ++k) {
        int nodeCount = 1 << k;
        int sizePerNode = n >> k;
        std::cout << k << '\t' << nodeCount << '\t' << sizePerNode
                  << '\t' << biayaPerLevel[k] << '\n';
        total += biayaPerLevel[k];
    }
    std::cout << "Total = " << total
              << " (n log n = " << 1LL * n * maxLevel << ")\n";
    return 0;
}

Output yang Dihasilkan:

text 
Level   Node    Size/Node       Biaya
0       1       16      16
1       2       8       16
2       4       4       16
3       8       2       16
4       16      1       16
Total = 80 (n log n = 80)

Bedah Kode Baris-per-Baris #

  1. Baris for (int k = 0; (n >> k) >= 1; ++k): iterasi dari level 0 sampai level saat n / 2^k = 1, yaitu k = log₂ n. Operator >> adalah right shift, ekuivalen dengan pembagian 2.
  2. Baris int nodeCount = 1 << k;: jumlah node pada level k, yaitu 2^k. Operator << adalah left shift, ekuivalen dengan perkalian 2.
  3. Baris biayaPerLevel[k] = 1LL * nodeCount * sizePerNode;: biaya total pada level k adalah perkalian jumlah node dengan ukuran tiap node. Cast 1LL memaksa long long agar n = 1024 tidak overflow saat k besar.
  4. Output: setiap level berkontribusi n = 16 biaya. Dengan 5 level (level 0 hingga 4), total biaya = 5 × 16 = 80 = n log n. Inilah inti klaim bahwa T(n) = 2T(n/2) + O(n) = Θ(n log n).
  5. Implikasi: visualisasi pohon memberi intuisi yang jelas tentang kontribusi tiap level. Untuk algoritma divide and conquer dengan f(n) = n^k, pola ini menghasilkan solusi yang berbeda tergantung relasi k dengan log_b a.

Recurrence Tidak Standar #

Beberapa recurrence tidak berbentuk a · T(n/b) + f(n) dan memerlukan analisis khusus:

Contoh: T(n) = T(√n) + O(1) #

Misalkan m = log₂ n, sehingga n = 2^m. Maka √n = 2^(m/2), sehingga T(2^m) = T(2^(m/2)) + O(1). Definisikan S(m) = T(2^m), maka S(m) = S(m/2) + O(1). Solusi: S(m) = O(log m) = O(log log n). Jadi T(n) = O(log log n).

Contoh: T(n) = 2T(n/2) + n log n #

Recurrence ini tidak dapat langsung diselesaikan dengan Master Theorem (kasus 2 memerlukan f(n) = Θ(n^k) dengan k = log_b a). Substitute menghasilkan T(n) = Θ(n log² n).

Kode: Verifikasi Numerik Berbagai Recurrence #

cpp 
#include <iostream>

// T n = T n/2 + O 1 -> O log n
long long binSearch(long long n) {
    if (n <= 1) return 1;
    return 1 + binSearch(n / 2);
}

// T n = 2T n/2 + O n -> O n log n
long long mergeSortCost(long long n) {
    if (n <= 1) return 1;
    return 2 * mergeSortCost(n / 2) + n;
}

// T n = T n-1 + O n -> O n^2
long long selectionSortCost(long long n) {
    if (n <= 1) return 1;
    return selectionSortCost(n - 1) + n;
}

int main() {
    long long n = 32;
    std::cout << "n = " << n << '\n';
    std::cout << "Binary search (T n = T n/2 + 1)   : " << binSearch(n)
              << "  (log2 n + 1 = " << 6 << ")\n";
    std::cout << "Merge sort (T n = 2T n/2 + n)      : " << mergeSortCost(n)
              << "  (n log n = " << n * 5 << ")\n";
    std::cout << "Selection sort (T n = T n-1 + n)  : " << selectionSortCost(n)
              << "  (n^2/2 = " << n * n / 2 << ")\n";
    return 0;
}

Output yang Dihasilkan:

text 
n = 32
Binary search (T n = T n/2 + 1)   : 6  (log2 n + 1 = 6)
Merge sort (T n = 2T n/2 + n)     : 192  (n log n = 160)
Selection sort (T n = T n-1 + n)  : 528  (n^2/2 = 512)

Bedah Kode Baris-per-Baris #

  1. Fungsi binSearch: mengimplementasikan recurrence T(n) = T(n/2) + 1 dengan T(1) = 1. Output 6 sesuai dengan log₂ 32 + 1 = 5 + 1 = 6.
  2. Fungsi mergeSortCost: mengimplementasikan T(n) = 2T(n/2) + n dengan T(1) = 1. Output 192 mendekati n log n = 160 tetapi lebih besar karena base case T(1) = 1 (bukan 0) dan konstanta tambahan n per level.
  3. Fungsi selectionSortCost: mengimplementasikan T(n) = T(n-1) + n. Output 528 mendekati n²/2 = 512. Selisih berasal dari base case dan konstanta. Untuk n besar, rasio mendekati 1/2.
  4. Implikasi: implementasi langsung dari recurrence memberi validasi numerik terhadap solusi teoritis. Selisih kecil disebabkan oleh base case dan konstanta yang diabaikan dalam Big-Theta.

Ringkasan #

  • Recurrence relation menggambarkan T(n) dalam bentuk T pada input lebih kecil.
  • Pola umum: T(n) = a · T(n/b) + f(n) (divide and conquer), T(n) = T(n-1) + f(n) (linier), T(n) = T(n-1) + T(n-2) + f(n) (fibonacci-like).
  • Substitution method: tebak solusi lalu buktikan dengan induksi.
  • Recursion tree: visualisasi pohon, hitung biaya per level lalu jumlahkan.
  • Beberapa recurrence tidak standar (misal T(√n) atau T(n) = 2T(n/2) + n log n) memerlukan analisis khusus.

Pada Chapter berikutnya kita akan mempelajari Master Theorem — formula siap pakai untuk menyelesaikan recurrence berbentuk T(n) = a · T(n/b) + f(n) dengan tiga kasus berbeda.