Recurrence সমাধান — substitution আর recursion tree

১ · Recurrence কী — নিজের ছোট রূপ দিয়ে লেখা হিসাব

পর্ব ০৭-এ দেখেছেন, recursion-এ একটি ফাংশন নিজেকেই আবার ডাকে — ছোট ইনপুটে। এবার প্রশ্ন হলো, এমন ফাংশন চলতে কত সময় নেয়? সাধারণ loop-এর বেলায় আমরা গুনতাম: loop কতবার ঘোরে, প্রতিবারে কত কাজ। কিন্তু রিকার্সিভ ফাংশনের ভেতরে তো সে নিজেই আছে! তার সময় জানতে হলে আগে নিজের সময়টাই জানতে হয়।

কেন এটা এত গুরুত্বপূর্ণ? কারণ কোর্সের সামনের বেশিরভাগ ভালো অ্যালগরিদম — binary search, merge sort, quick sort, heap, segment tree, DFS, Karatsuba, Strassen, dynamic programming — সবই রিকার্সিভ। তাদের সময় বোঝার প্রধান পথ recurrence. এই পর্বে আমরা তিনটি হাতিয়ার শিখব:

চতুর্থ একটি হাতিয়ার — master theorem — আসবে পর্ব ০৯-এ। সেটি অনেক recurrence এক লাইনে সমাধান করে, কিন্তু কেন কাজ করে তা বুঝতে হলে এই পর্বের recursion tree লাগবেই।

২ · কোড দেখে recurrence লেখা

নিয়মটি সহজ। একটি রিকার্সিভ ফাংশনের সময় T(n) = (প্রতিটি রিকার্সিভ ডাকের সময় যোগ) + (ডাকের বাইরে ফাংশনটি নিজে যা কাজ করে)। তিনটি প্রশ্ন করুন:

1. কতবার নিজেকে ডাকে? — এটি সামনের গুণক (যেমন 2T-এর 2).
2. প্রতিটি ডাকে ইনপুট কত বড়? — n/2, n/3, n−1, n−2…
3. ডাকের বাইরে কত কাজ? — ভাগ করা, জোড়া দেওয়া, loop — এটি শেষের পদ।

নিচের ডায়াগ্রামে merge sort-এর pseudocode লাইন ধরে ধরে পড়া হচ্ছে, আর ডান দিকে recurrence তৈরি হচ্ছে। “পরে” চাপুন:

1mergeSort(A, lo, hi):   // n = hi - lo2  if n <= 1: return3  mid = (lo + hi) / 24  mergeSort(A, lo, mid)5  mergeSort(A, mid, hi)6  merge(A, lo, mid, hi)

এবার একই নিয়মে আরও চারটি বিখ্যাত রিকার্সিভ ফাংশন দেখুন (নিচের সারণিতে merge sort-সহ পাঁচটি)। কোডটি চালানোর জন্য নয় — শুধু গঠন দেখার জন্য (C++-ধাঁচের pseudocode, ০-ভিত্তিক index):

// Pseudocode
search(A, lo, hi, x):            // binary search, n = hi - lo
    if n == 0: return -1
    mid = (lo + hi) / 2
    if A[mid] == x: return mid
    if A[mid] < x: return search(A, mid + 1, hi, x)   // ONE call, half size
    return search(A, lo, mid, x)

fib(n):                          // naive Fibonacci
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)   // TWO calls, sizes n-1 and n-2

hanoi(n, from, to, via):         // Tower of Hanoi
    if n == 0: return
    hanoi(n - 1, from, via, to)      // move n-1 disks out of the way
    move disk n from -> to           // 1 move
    hanoi(n - 1, via, to, from)      // put them back on top

sortRec(A, n):                   // recursive selection sort
    if n <= 1: return
    swap the largest of A[0..n-1] into A[n-1]   // n steps
    sortRec(A, n - 1)

খেয়াল করুন, দেখতে প্রায় একই রকম দুটি recurrence-এর উত্তর কত আলাদা হতে পারে। T(n/2) + 1 হলো Θ(log n) — দশ লাখ ইনপুটে মাত্র ২০-২১ ধাপ। কিন্তু 2T(n−1) + 1 হলো Θ(2ⁿ) — n = 64 হলেই সংখ্যাটা কল্পনার বাইরে। পার্থক্য শুধু “অর্ধেক” বনাম “এক কম”, আর “একটি ডাক” বনাম “দুটি ডাক”। এজন্যই recurrence অনুমানে নয়, হিসাব করে সমাধান করতে হয়।

৩ · Base case আর floor-ceiling — কেন সাধারণত বাদ দেওয়া যায়

বইয়ে প্রায়ই লেখা থাকে শুধু T(n) = 2T(n/2) + n — base case নেই, floor-ceiling নেই। এটা কি ফাঁকি? না — দুটি সুনির্দিষ্ট কারণে এগুলো সাধারণত Θ-উত্তর বদলায় না।

Base case শুধু ধ্রুবক বদলায়

রিকার্সিভ অ্যালগরিদমে ছোট ইনপুটে (ধরুন n ≤ ১০) কাজ সবসময় কোনো ধ্রুবক সময়ে শেষ হয়। তাই আমরা ধরে নিই “যথেষ্ট ছোট n-এ T(n) = Θ(1)”. ধ্রুবকটি ১ হোক বা ১০০, উত্তরে শুধু একটি গুণক বা নিম্নমানের পদ বদলায়। যেমন T(n) = 2T(n/2) + n, T(1) = c হলে (n দুইয়ের ঘাত ধরে) ঠিক উত্তর n·lg n + c·n — c যা-ই হোক, এটি Θ(n log n). এখানে lg মানে log₂.

Floor-ceiling: দুইয়ের ঘাতের মাঝে চাপা দেওয়া

প্রথমে উদাহরণ। T(n) = T(⌊n/2⌋) + 1, T(1) = 1. হাতে হিসাব করুন: T(1) = 1, T(2) = 2, T(3) = T(1) + 1 = 2, T(4) = 3, T(7) = T(3) + 1 = 3, T(8) = 4. নিয়মটি দাঁড়ায় T(n) = ⌊lg n⌋ + 1 — floor থাকা সত্ত্বেও উত্তর Θ(log n), ঠিক যেমন n দুইয়ের ঘাত ধরে পেতাম।

সাধারণ যুক্তিটি “চাপা দেওয়া” (sandwich). ধরুন T একটি বাড়তে থাকা ফাংশন (বড় ইনপুটে সময় কম লাগে না — প্রায় সব অ্যালগরিদমেই সত্য)। যেকোনো n-এর জন্য এমন k আছে যে 2^k ≤ n < 2^k+1. তাহলে T(2^k) ≤ T(n) ≤ T(2^(k+1)). Merge sort-এ T(2^k) = Θ(2^k·k), আর 2^k+1 বড়জোর n-এর দ্বিগুণ। ইনপুট দ্বিগুণ করলে n log n বড়জোর দ্বিগুণের সামান্য বেশি হয় — ধ্রুবক গুণক মাত্র। তাই দুই পাশই Θ(n log n), মাঝখানের T(n)-ও তাই।

৪ · Unrolling — খুলে খুলে লেখার পদ্ধতি

সবচেয়ে সরাসরি পদ্ধতির নাম iteration বা unrolling method. পেঁয়াজের খোসা ছাড়ানোর মতো: T(n)-এর ভেতরে T(n−1)-এর সংজ্ঞা বসান, তার ভেতরে T(n−2)-এর… কয়েক ধাপ পর একটি প্যাটার্ন চোখে পড়বে। তখন “i ধাপ পরে” সাধারণ রূপ লিখে i-কে এমন বসান যাতে base case-এ পৌঁছান।

Tower of Hanoi দিয়ে দেখি: T(n) = 2T(n−1) + 1, T(1) = 1 (একটি চাকতি এক চালেই সরে)।

1T(n) = 2T(n-1) + 12     = 4T(n-2) + 2 + 13     = 8T(n-3) + 4 + 2 + 14     = 2^i·T(n-i) + (2^i - 1)5i=n-1: 2^(n-1)·T(1) + 2^(n-1) - 16     = 2^n - 1  =  Θ(2^n)

একই পদ্ধতিতে বাকি দুটি এক-শাখার recurrence মিনিটেই শেষ হয়:

• Binary search: T(n) = T(n/2) + 1 = T(n/4) + 2 = T(n/8) + 3 = … = T(n/2ⁱ) + i. n/2ⁱ = 1 হলে i = lg n, তাই T(n) = T(1) + lg n = lg n + 1 = Θ(log n).
• রিকার্সিভ selection sort: T(n) = T(n−1) + n = T(n−2) + (n−1) + n = … = T(1) + 2 + 3 + … + n. T(1) = 1 ধরলে যোগফল n(n+1)/2 = Θ(n²). এটা সেই পরিচিত “১ থেকে n-এর যোগফল” — insertion sort-এর worst case-ও ঠিক এই আকারের।

৫ · Recursion tree — স্তর ধরে খরচ যোগ

Recursion tree-এ প্রতিটি রিকার্সিভ ডাক একটি নোড। নোডের ভেতরে লেখা হয় সেই ডাকের নিজস্ব কাজ — অর্থাৎ recurrence-এর শেষ পদ, যেটি রিকার্সিভ ডাকের বাইরে। তারপর তিনটি প্রশ্ন:

1. প্রতি স্তরের মোট খরচ কত? (নোডের সংখ্যা × প্রতিটির কাজ)
2. স্তর কয়টি? (আকার কতবার ভাগ হলে ১-এ নামে)
3. সব যোগ করলে কত? — শেষ স্তরের leaf-গুলোসহ।

উদাহরণ ১: T(n) = 2T(n/2) + n — প্রতিটি স্তর সমান

0          n1     n/2     n/22  n/4  n/4  n/4  n/4⋮  . . . . . . . . .k  1 1 1 1 ... 1 1 1

উদাহরণ ২: T(n) = T(n/3) + T(2n/3) + n — অসমান ভাগ

Quick sort যদি প্রতিবার ইনপুটকে ১ : ২ অনুপাতে ভাগ করে, তার সময় দাঁড়ায় এই recurrence-এ (পর্ব ২২-এ বিস্তারিত)। গাছটি এবার বাঁকা — বাঁ দিকের শাখা দ্রুত শেষ হয়, ডান দিকেরটা দেরিতে। Master theorem এটি সরাসরি সামলাতে পারে না, কিন্তু recursion tree পারে:

0             n1      n/3          2n/32  n/9  2n/9    2n/9  4n/9L  বাঁ পথ: log₃ n স্তরে শেষR  ডান পথ: log₃/₂ n স্তরে শেষ

একটি সূক্ষ্ম বিষয়: ওপরের সীমায় leaf-গুলোর খরচ কি আলাদা করে যোগ করতে হলো না? না, কারণ প্রতিটি স্তরে টুকরোগুলোর আকারের যোগফল বড়জোর n, আর প্রতিটি টুকরো অন্তত ১ আকারের — তাই এক স্তরে বড়জোর n টি নোড, leaf-সহ। এই খুঁটিনাটি পরীক্ষার খাতায় এক লাইনে লিখে দিলে প্রমাণ সম্পূর্ণ হয়।

উদাহরণ ৩: T(n) = 3T(n/4) + n² — ওপরের স্তর ভারী

0            n²1   (n/4)²  (n/4)²  (n/4)²2   9 টি নোড, প্রতিটি (n/16)²i   3^i টি নোড, প্রতিটি (n/4^i)²k   3^k = n^0.79 টি leaf

নিচের টুলে নিজেই a, b, c বদলে T(n) = aT(n/b) + n^c-এর প্রতিটি স্তরের খরচ দেখুন। কোন স্তর ভারী, তা সংখ্যাগুলোই বলে দেবে:

// a = how many subproblems, b = size shrinks by b, c = work per node is (size)^c
function levelTable(a, b, c, n) {
  console.log(`T(n) = ${a}T(n/${b}) + n^${c},  n = ${n}`);
  let sum = 0, size = n, nodes = 1, d = 0;
  while (size >= 1) {
    const cost = nodes * size ** c;            // total work on this level
    sum += cost;
    console.log(`  level ${d}: ${nodes} nodes x size ${size} -> cost ${cost}`);
    nodes *= a; size /= b; d++;
  }
  console.log(`  total = ${sum}  (total / n^${c} = ${(sum / n ** c).toFixed(3)})`);
}
levelTable(2, 2, 1, 16);    // merge sort: every level equal
levelTable(3, 4, 2, 256);   // root-heavy
levelTable(4, 2, 1, 16);    // leaf-heavy

৬ · Substitution — অনুমান করুন, induction দিয়ে প্রমাণ করুন

Recursion tree চমৎকার অনুমান দেয়, কিন্তু “…” আর “ধারা চলছে” লেখা ছবি সবসময় কঠোর প্রমাণ নয়। কঠোর প্রমাণের মানদণ্ড হলো substitution method: দুই ধাপ —

1. উত্তরের রূপ অনুমান করুন (যেমন T(n) ≤ c·n lg n), যেখানে c একটি এখনো-অজানা ধ্রুবক।
2. Mathematical induction দিয়ে প্রমাণ করুন: ধরে নিন n-এর চেয়ে ছোট সব k-এর জন্য অনুমানটি সত্য (এটি inductive hypothesis), তারপর recurrence-এ বসিয়ে দেখান n-এর জন্যও সত্য — একই c দিয়ে। শেষে base case মিলিয়ে নিন।

পূর্ণ উদাহরণ: merge sort-এর O(n log n)

Recurrence: T(n) = 2T(⌊n/2⌋) + n, T(1) = 1. দাবি: n ≥ 2 হলে T(n) ≤ c·n lg n, কোনো ধ্রুবক c-এর জন্য।

• Inductive step: ধরে নিই ⌊n/2⌋-এর জন্য দাবিটি সত্য। তাহলে T(n) ≤ 2·c⌊n/2⌋·lg⌊n/2⌋ + n ≤ 2·c(n/2)·lg(n/2) + n = cn(lg n − 1) + n = cn lg n − cn + n. এটি ≤ cn lg n হবে, যদি −cn + n ≤ 0, অর্থাৎ c ≥ 1.
• Base case: n = 1-এ সমস্যা — c·1·lg 1 = 0, অথচ T(1) = 1. সমাধান: base হিসেবে n = 2 আর n = 3 নিন (n ≥ 4 হলে ⌊n/2⌋ ≥ 2, তাই induction কখনো n = 1-এ নামে না)। T(2) = 2·1 + 2 = 4 ≤ c·2·1, আর T(3) = 2·1 + 3 = 5 ≤ c·3·lg 3 ≈ 4.75c. দুটোই c ≥ 2 হলে খাটে।
• উপসংহার: c = 2 নিলে সব n ≥ 2-এ T(n) ≤ 2n lg n, অর্থাৎ T(n) = O(n log n). নিচের সীমাও (Ω) একইভাবে প্রমাণ করা যায় — দুটো মিলে Θ.

যখন অনুমান ঠিক, কিন্তু প্রমাণ আটকে যায়

এবার উল্টো সমস্যা। T(n) = 2T(n/2) + 1, T(1) = 1 — একটি গাছ, যার প্রতিটি নোডে ধ্রুবক কাজ (যেমন রিকার্শন দিয়ে array-র সর্বোচ্চ মান খোঁজা)। নোড আছে প্রায় 2n টি, তাই উত্তর O(n) হওয়ারই কথা। কিন্তু সরাসরি প্রমাণ করতে গেলে কী হয়, দেখুন:

1ধরি: T(k) ≤ c·k  (সব k < n)2T(n) ≤ 2·c(n/2) + 1 = cn + 13cn + 1 ≤ cn ?   কখনোই না  ✗4নতুন: T(k) ≤ c·k − d5T(n) ≤ 2(c·n/2 − d) + 1
          = cn − 2d + 1 ≤ cn − d  ✓6base: T(1) = 1 ≤ c − d  → c=2, d=1 ✓

অনুমান কোথা থেকে আসে? তিনটি উৎস: (১) recursion tree, (২) চেনা recurrence-এর সাথে মিল (যেমন T(n) = 2T(n/2 + 17) + n দেখতে merge sort-এর মতো, উত্তরও Θ(n log n)), (৩) ছোট প্রোগ্রামে সংখ্যা হিসাব করে প্রবণতা দেখা — পরের অংশে ঠিক এটাই করব। আর অনুমান খুব আলগা হলে (যেমন O(n²) অনুমান করলেন যেখানে আসল উত্তর n log n) প্রমাণ সফল হবে ঠিকই, কিন্তু সেটি দুর্বল সীমা। তাই সাধারণত ওপর আর নিচ দুই দিক থেকে চেপে আসল Θ খুঁজে বের করতে হয়।

৭ · সংখ্যা দিয়ে যাচাই — অনুপাত কি স্থির হয়?

হাতে কাগজে সমাধান করার পর একটি সহজ পরীক্ষা: recurrence-টি সরাসরি প্রোগ্রামে হিসাব করুন, তারপর আপনার অনুমান করা উত্তর দিয়ে ভাগ করুন। n বাড়ার সাথে অনুপাত যদি একটি ধ্রুবকের দিকে স্থির হয়, অনুমান Θ হিসেবে ঠিক পথে। যদি অনুপাত বাড়তেই থাকে বা শূন্যের দিকে নামে, অনুমান ভুল।

নিচের প্রোগ্রাম চারটি recurrence হিসাব করে n = 2^k-এ (floor সহ, base case T(n) = 1 যখন n ≤ 1). একই উপ-সমস্যা বারবার হিসাব না করতে মান মনে রাখা হয় — এই কৌশলের নাম memoization (পর্ব ৫২-এ বিস্তারিত)। আপনার পছন্দের ভাষার ট্যাব বেছে নিন:

#include <cstdio>
#include <map>
using ll = long long;
std::map<ll, ll> memo[4];

ll T(int id, ll n) {                                   // base case: T = 1 for n <= 1
    if (n <= 1) return 1;
    if (auto it = memo[id].find(n); it != memo[id].end()) return it->second;
    ll r;
    if (id == 0)      r = T(0, n / 2) + 1;                    // A: binary search
    else if (id == 1) r = 2 * T(1, n / 2) + n;                // B: merge sort
    else if (id == 2) r = T(2, n / 3) + T(2, 2 * n / 3) + n;  // C: uneven split
    else              r = 3 * T(3, n / 4) + n * n;            // D: 3T(n/4) + n^2
    return memo[id][n] = r;
}

int main() {
    std::printf("%3s %8s %7s %7s %7s %7s\n", "k", "n", "A/lgn", "B/nlgn", "C/nlgn", "D/n^2");
    for (int k = 4; k <= 20; k += 4) {
        ll n = 1LL << k;
        double lg = k;
        std::printf("%3d %8lld %7.4f %7.4f %7.4f %7.4f\n", k, n, T(0, n) / lg,
                    T(1, n) / (n * lg), T(2, n) / (n * lg), T(3, n) / double(n * n));
    }
}

  k        n   A/lgn  B/nlgn  C/nlgn   D/n^2
  4       16  1.2500  1.2500  1.0469  1.2227
  8      256  1.1250  1.1250  1.0439  1.2305
 12     4096  1.0833  1.0833  1.0475  1.2308
 16    65536  1.0625  1.0625  1.0634  1.2308
 20  1048576  1.0500  1.0500  1.0729  1.2308

from functools import cache

@cache
def T(i, n):                                       # base case: T = 1 for n <= 1
    if n <= 1:
        return 1
    if i == 0: return T(0, n // 2) + 1                      # A: binary search
    if i == 1: return 2 * T(1, n // 2) + n                  # B: merge sort
    if i == 2: return T(2, n // 3) + T(2, 2 * n // 3) + n   # C: uneven split
    return 3 * T(3, n // 4) + n * n                         # D: 3T(n/4) + n^2

print("%3s %8s %7s %7s %7s %7s" % ("k", "n", "A/lgn", "B/nlgn", "C/nlgn", "D/n^2"))
for k in range(4, 21, 4):
    n = 1 << k
    print("%3d %8d %7.4f %7.4f %7.4f %7.4f" % (k, n, T(0, n) / k,
          T(1, n) / (n * k), T(2, n) / (n * k), T(3, n) / (n * n)))

  k        n   A/lgn  B/nlgn  C/nlgn   D/n^2
  4       16  1.2500  1.2500  1.0469  1.2227
  8      256  1.1250  1.1250  1.0439  1.2305
 12     4096  1.0833  1.0833  1.0475  1.2308
 16    65536  1.0625  1.0625  1.0634  1.2308
 20  1048576  1.0500  1.0500  1.0729  1.2308

এবার সারণিটি পড়ুন:

• A আর B (binary search, merge sort): অনুপাত 1.25 → 1.05, ধীরে ধীরে ১-এর দিকে। কারণ আসল উত্তর lg n + 1 আর n(lg n + 1), তাই অনুপাত ঠিক 1 + 1/lg n. স্থির হচ্ছে — Θ(log n) আর Θ(n log n) নিশ্চিত।
• D (3T(n/4) + n²): অনুপাত 1.2308-এ এসে থেমে গেছে — recursion tree-র (16/13)·n² হুবহু! মূল-ভারী গাছে নিচের স্তরগুলো দ্রুত নগণ্য হয়, তাই এত দ্রুত স্থির।
• C (T(n/3) + T(2n/3) + n): 1.04 থেকে 1.07-এর মধ্যে ঘুরছে, খুব ধীরে বাড়ছে। এটি বাড়তে বাড়তে প্রায় 1.089-এর কাছে থামে (আরও গভীরে বক্সে কারণ দেখুন)। floor-এর কারণে একটু ওঠানামাও আছে। অনুপাত অসীমের দিকে ছুটছে না, শূন্যের দিকেও নামছে না — তাই Θ(n log n) ঠিক।

৮ · চলক বদল আর linear recurrence — √n আর Fibonacci

চলক বদল: T(n) = 2T(√n) + lg n

কিছু recurrence অচেনা দেখায়, কিন্তু একটু রূপ বদলালেই চেনা রূপে আসে। এই কৌশলের নাম change of variables. এখানে ইনপুট প্রতিবার বর্গমূলে নামছে — n, √n, n^1/4, … এমন আচরণ দেখা যায় van Emde Boas tree-র মতো কিছু উন্নত স্ট্রাকচারে।

1. m = lg n ধরুন, অর্থাৎ n = 2^m. তাহলে √n = 2^m/2, আর recurrence হয়: T(2^m) = 2T(2^m/2) + m.
2. নতুন ফাংশন S(m) = T(2^m) সংজ্ঞায়িত করুন। তাহলে S(m) = 2S(m/2) + m — এ তো merge sort!
3. তাই S(m) = Θ(m log m). ফেরত বসালে T(n) = Θ(lg n · lg lg n).

একই কৌশলে T(n) = T(√n) + 1 হয় S(m) = S(m/2) + 1 = Θ(log m), অর্থাৎ T(n) = Θ(log log n) — অবিশ্বাস্য রকম ধীরে বাড়ে।

Linear homogeneous recurrence আর golden ratio

Fibonacci-র F(n) = F(n−1) + F(n−2) ভাগ-করে-জয় নয়; এখানে আকার ১ বা ২ করে কমে। এমন recurrence-কে বলে linear homogeneous (প্রতিটি পদ আগের পদগুলোর ধ্রুবক-গুণিত যোগফল, বাড়তি কোনো পদ নেই)। কৌশলটি হলো উত্তরের রূপ অনুমান করা: F(n) = rⁿ.

• বসালে rⁿ = rⁿ⁻¹ + rⁿ⁻², দুই দিকে rⁿ⁻² দিয়ে ভাগ করে পাই r² = r + 1 — এটিই characteristic equation.
• মূল দুটি: φ = (1 + √5)/2 ≈ 1.618 (golden ratio) আর ψ = (1 − √5)/2 ≈ −0.618.
• সাধারণ সমাধান: F(n) = α·φⁿ + β·ψⁿ. F(0) = 0, F(1) = 1 বসিয়ে α = 1/√5, β = −1/√5. ফল: F(n) = (φⁿ − ψⁿ)/√5 — বিখ্যাত Binet-এর সূত্র। |ψ| < 1, তাই ψⁿ দ্রুত শূন্যের দিকে যায়, আর F(n) হলো φⁿ/√5-এর নিকটতম পূর্ণসংখ্যা।

এবার সরল fib(n)-এর সময়: C(n) = C(n−1) + C(n−2) + 1 (ডাকের সংখ্যা)। শেষের “+১” সরাতে U(n) = C(n) + 1 ধরুন: তাহলে U(n) = U(n−1) + U(n−2) — আবার Fibonacci-র রূপ! U(0) = U(1) = 2 থেকে পাওয়া যায় U(n) = 2F(n+1), অর্থাৎ C(n) = 2F(n+1) − 1 = Θ(φⁿ). নিচের প্রোগ্রাম আসল কোড চালিয়ে ডাক আর চাল গোনে:

#include <cmath>
#include <cstdio>

long long calls = 0, moves = 0;

long long fib(int n) {                           // calls: C(n) = C(n-1) + C(n-2) + 1
    ++calls;
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

void hanoi(int n, int from, int to, int via) {   // moves: T(n) = 2T(n-1) + 1
    if (n == 0) return;
    hanoi(n - 1, from, via, to);
    ++moves;                                     // move the largest disk
    hanoi(n - 1, via, to, from);
}

int main() {
    const double phi = (1 + std::sqrt(5.0)) / 2;
    std::printf("%3s %10s %10s %11s\n", "n", "fib_calls", "hanoi", "calls/phi^n");
    for (int n = 5; n <= 25; n += 5) {
        calls = moves = 0; fib(n); hanoi(n, 1, 3, 2);
        std::printf("%3d %10lld %10lld %11.4f\n", n, calls, moves, calls / std::pow(phi, n));
    }
}

  n  fib_calls      hanoi calls/phi^n
  5         15         31      1.3525
 10        177       1023      1.4391
 15       1973      32767      1.4465
 20      21891    1048575      1.4471
 25     242785   33554431      1.4472

৯ · AI-এর যুগে recurrence

AI-কে “এই কোডের time complexity কত?” জিজ্ঞেস করলে উত্তর আসে সেকেন্ডে, আত্মবিশ্বাসী ভাষায়। সমস্যা হলো, recurrence-এর প্রশ্নে AI প্রায়ই চেনা প্যাটার্নের সাথে মিলিয়ে উত্তর দেয় — আর দেখতে একই রকম দুটি recurrence-এর উত্তর যে একেবারে আলাদা হতে পারে, সেটা এই পর্বেই দেখেছেন। নিচের ভুলগুলো বারবার দেখা যায়:

AI-এর দেওয়া complexity হাতে পেলে — যাচাইয়ের চেকলিস্ট

• কোড দেখে নিজেই recurrence লিখেছি — ডাকের সংখ্যা, আকার আর বাইরের কাজ আলাদা করে
• ছোট n-এ (১ থেকে ৮) recurrence হাতে হিসাব করে AI-এর সূত্রে বসিয়ে মিলিয়েছি
• Master theorem ব্যবহার হলে নিশ্চিত হয়েছি যে recurrence-টি সত্যিই T(n/b) রূপে আছে
• Induction প্রমাণে শেষ লাইনে ঠিক একই ধ্রুবক এসেছে, “+ n” বা “+ ১” লুকানো নেই
• ছোট প্রোগ্রামে T(n) ÷ অনুমান অনুপাত চালিয়ে দেখেছি — স্থির হচ্ছে, বাড়ছে না, শূন্যেও নামছে না
• আসল কোডে ডাক বা ধাপ গুনে (counter বসিয়ে) recurrence-এর মানের সাথে মিলিয়েছি