Master theorem — divide and conquer-এর হিসাব এক লাইনে

১ · এক ছাঁচে অনেক অ্যালগরিদম — T(n) = aT(n/b) + f(n)

পর্ব ০৮-এ আপনি recurrence সমাধান করেছেন দুইভাবে — অনুমান করে প্রমাণ (substitution method) আর recursion tree এঁকে তলায় তলায় যোগ। দুটোই শক্তিশালী, কিন্তু প্রতিবার গাছ আঁকা, ধারা যোগ করা, তারপর induction — পরীক্ষার হলে বা ইন্টারভিউর টেবিলে এত সময় থাকে না। এই পর্বে সেই পুরো খাটুনি এক লাইনে নামিয়ে আনব।

একটু খেয়াল করলে দেখবেন, divide and conquer অ্যালগরিদমগুলোর recurrence প্রায় সবসময় একই চেহারার:

• a — একটি সমস্যা থেকে কয়টি ছোট সমস্যা (subproblem) তৈরি হয়, অর্থাৎ ফাংশন নিজেকে কয়বার ডাকে। a ≥ 1 একটি ধ্রুবক।
• b — প্রতিটি ছোট সমস্যা মূলের কত ভাগের এক। b > 1 একটি ধ্রুবক।
• f(n) — রিকার্শনের বাইরের কাজ: সমস্যা ভাঙা আর ছোট উত্তরগুলো জোড়া দেওয়ার মোট খরচ।

পরিচিত কয়েকটি অ্যালগরিদম এই ছাঁচে বসিয়ে দেখুন:

কোড থেকে a, b আর f(n) পড়া

পরীক্ষায় প্রায়ই recurrence দেওয়া থাকে না — দেওয়া থাকে একটি ফাংশন। তখন তিনটি প্রশ্ন করুন: নিজেকে কয়বার ডাকছে (a)? প্রতিটি ডাকে ইনপুট কত ছোট হচ্ছে (b)? আর ডাকগুলোর বাইরে কত কাজ হচ্ছে (f)? নিচের ফাংশনটি একটি range-এর সব সংখ্যার কিছু হিসাব করে:

long long solve(int lo, int hi) {            // n = hi - lo
    if (hi - lo <= 1) return w[lo];          // base case: Θ(1)
    int mid = (lo + hi) / 2;
    long long x = solve(lo, mid);            // T(n/2)
    long long y = solve(mid, hi);            // T(n/2)
    long long s = 0;
    for (int i = lo; i < hi; ++i) s += w[i]; // Θ(n) outside the calls
    return x + y + s;
}

দুটি ডাক, প্রতিটি অর্ধেক আকারে, আর একটি Θ(n) লুপ — তাই T(n) = 2T(n/2) + Θ(n). তিনটি ফাঁদ থেকে সাবধান থাকুন। এক: লুপের ভেতরে রিকার্সিভ ডাক থাকলে a হয় লুপ যতবার ঘোরে ততটি। দুই: একই আর্গুমেন্টে দুবার ডাকলেও (memoization না থাকলে) দুটি ডাকই গুনতে হবে। তিন: লুকানো খরচ। Python-এ a[:mid] লিখলে তালিকার একটি নতুন কপি তৈরি হয়, যার খরচ Θ(n). তাই slicing দিয়ে লেখা “binary search” আসলে T(n) = T(n/2) + Θ(n) — case 3, Θ(n)! ইনডেক্স (lo, hi) পাঠালে সেটি আবার Θ(log n) হয়ে যায়। একটি অদৃশ্য কপি পুরো complexity বদলে দিতে পারে।

২ · Recursion tree থেকে অন্তর্দৃষ্টি — কোন তলায় খরচ বেশি

Master theorem কোনো জাদুর সূত্র নয়। এটি আসলে recursion tree-র যোগফলকে আগে থেকেই একবার সাধারণভাবে করে রাখা। তাই সূত্র মুখস্থ করার আগে গাছটি মাথায় বসিয়ে নিন। নিচের ডায়াগ্রামে প্রথমে সাধারণ চিত্র, তারপর n = 16 নিয়ে তিনটি আলাদা recurrence-এর গাছ — প্রতিটি তলার মোট খরচ খেয়াল করুন।

level 0 :  1 node      size n       cost f(n)
level 1 :  a nodes     size n/b     cost a·f(n/b)
level 2 :  a^2 nodes   size n/b^2   cost a^2·f(n/b^2)
   ...
level j :  a^j nodes   size n/b^j   cost a^j·f(n/b^j)
   ...
leaves  :  a^(log_b n) nodes, each Θ(1)

size at level j = n / b^j = 1   ->   j = log_b n
leaves = a^(log_b n) = n^(log_b a)

example  a = 4, b = 2:  4^(log_2 n) = n^2
example  a = 3, b = 2:  3^(log_2 n) = n^1.585
example  a = 1, b = 2:  1^(log_2 n) = 1

level 0:  [16]                 = 16
level 1:  [8]                  =  8
level 2:  [4]                  =  4
level 3:  [2]                  =  2
leaves :  [1]                  =  1
                       total   = 31   (= 2n - 1)

level 0:  [16]                 = 16
level 1:  [8][8]               = 16
level 2:  [4] x 4              = 16
level 3:  [2] x 8              = 16
leaves :  [1] x 16             = 16
                       total   = 80   (= n(lg n + 1))

level 0:  [16]                 =  16
level 1:  [8] x 4              =  32
level 2:  [4] x 16             =  64
level 3:  [2] x 64             = 128
leaves :  [1] x 256            = 256
                       total   = 496  (= 2n^2 - n)

level costs shrink  (T(n/2)+n)   ->  root wins    ->  Θ(f(n))
level costs equal   (2T(n/2)+n)  ->  every level  ->  Θ(f(n)·log n)
level costs grow    (4T(n/2)+n)  ->  leaves win   ->  Θ(n^(log_b a))

এখান থেকেই আসে watershed (জলবিভাজিকা) কথাটি। পাহাড়ের যে চূড়া ঠিক করে দেয় বৃষ্টির পানি কোন দিকে গড়াবে, তাকে বলে watershed. n^{log_b a} ঠিক তেমনি সীমারেখা: f(n) এর নিচে থাকলে খরচ পাতার দিকে গড়ায়, ওপরে থাকলে মূলের দিকে, আর সমান হলে সব তলায় সমানভাবে ছড়িয়ে থাকে। CLRS বইয়ের চতুর্থ সংস্করণ এই n^{log_b a}-কে বলে watershed function.

৩ · তিনটি case — CLRS-এর ভাষায় নির্ভুলভাবে

অন্তর্দৃষ্টি পেলেন, এবার নিয়মটি নির্ভুলভাবে লিখি — কারণ পরীক্ষায় শর্তগুলো ঠিকঠাক না লিখলে নম্বর কাটে, আর শর্ত না মিললে ভুল উত্তরও আসে। নিচের রূপটি Cormen, Leiserson, Rivest ও Stein-এর Introduction to Algorithms (সংক্ষেপে CLRS) বইয়ের।

প্রতিটি শর্তের পেছনের কারণ বুঝে নিন — তাহলে মুখস্থ করতে হবে না।

Case 1 — “polynomially ছোট” মানে কী

শুধু “f ছোট” বললে চলবে না; f-কে n^{log_b a}-এর চেয়ে অন্তত n^ε গুণক ছোট হতে হবে — যেখানে ε যত ছোটই হোক, একটি ধনাত্মক ধ্রুবক। কেন? কারণ তখনই তলার খরচগুলো জ্যামিতিক হারে বাড়ে (প্রতি তলায় b^ε গুণ), আর বাড়তে থাকা জ্যামিতিক ধারায় শেষ পদ — পাতাগুলো — জেতে। Strassen-এ f = n² আর watershed n^2.807: এখানে ε ≈ ০.৮, শর্ত পরিষ্কারভাবে মেলে।

Case 2 — সমান, log-এর গুণক পর্যন্ত

সবচেয়ে সাধারণ রূপে (k = 0): f(n) = Θ(n^{log_b a}) হলে প্রতিটি তলার খরচ সমান, তলা log_b n টি, তাই উত্তর Θ(n^{log_b a} log n). বর্ধিত রূপে f-এর সাথে log^k n গুণক থাকলেও চলে — তখন উত্তরে log-এর ঘাত এক বাড়ে। যেমন 2T(n/2) + n log n-এ k = 1, উত্তর Θ(n log² n). CLRS-এর তৃতীয় সংস্করণ পর্যন্ত মূল উপপাদ্যে শুধু k = 0 ছিল (বর্ধিত রূপটি অনুশীলনী হিসেবে ছিল); চতুর্থ সংস্করণ k ≥ 0 সরাসরি উপপাদ্যে এনেছে। তাই কোনো বই বা শিক্ষক “2T(n/2) + n log n-এ master theorem খাটে না” বললে বুঝবেন তিনি সংকীর্ণ রূপটির কথা বলছেন।

Case 3 — বড়, আর regularity শর্ত

f polynomially বড় হলে তলার খরচ সাধারণত কমতে থাকে, আর মূল জেতে। কিন্তু “সাধারণত” যথেষ্ট নয় — খরচ যেন নিশ্চিতভাবে জ্যামিতিক হারে কমে, সেটাই regularity শর্ত: a·f(n/b) ≤ c·f(n), c < 1. বাঁ দিক হলো তলা ১-এর মোট খরচ, ডান দিক মূলের খরচের c গুণ। তাহলে তলা j-এর খরচ ≤ c^j·f(n), আর সব তলার যোগফল ≤ f(n)/(1 − c) = O(f(n)). অন্যদিকে মূল একাই f(n), তাই T(n) = Θ(f(n)).

কেন সত্য — প্রমাণের রূপরেখা

অনেক পরীক্ষায় শুধু প্রয়োগ নয়, প্রমাণের মূল ভাবটিও চাওয়া হয়। সরলতার জন্য ধরি n হলো b-এর একটি ঘাত। অংশ ২-এর গাছ থেকে সরাসরি লেখা যায়:

প্রথম পদটি পাতাগুলোর খরচ, দ্বিতীয়টি ভেতরের সব তলার যোগফল (ধরুন g(n)). এখন তিন case আলাদা করে দেখি।

• Case 1: f(n/b^j) ≤ c(n/b^j)^{log_b a − ε} বসালে প্রতিটি পদ হয় c·n^{log_b a − ε}·(b^ε)^j — অনুপাত b^ε > 1 এর একটি বাড়তে থাকা জ্যামিতিক ধারা। তার যোগফল শেষ পদের ধ্রুবক গুণ, অর্থাৎ O(n^{log_b a − ε}·n^ε) = O(n^{log_b a}). পাতার পদের সাথে মিলিয়ে T(n) = Θ(n^{log_b a}).
• Case 2 (k = 0): প্রতিটি পদ a^j·(n/b^j)^{log_b a} = n^{log_b a}, কারণ a^j আর b^{j·log_b a} = a^j কেটে যায়। log_b n টি সমান পদ, তাই g(n) = Θ(n^{log_b a} log n). k > 0 হলে পদগুলো (log n − j)^k-এর মতো, আর Σ (log n − j)^k = Θ(log^k+1 n) — তাই বাড়তি একটি log.
• Case 3: regularity বারবার প্রয়োগ করলে a^jf(n/b^j) ≤ c^jf(n), তাই g(n) ≤ f(n)·(1 + c + c² + …) = f(n)/(1 − c). আর g(n) ≥ f(n) (প্রথম পদ)। পাতার পদ n^{log_b a} তো f-এর চেয়ে polynomially ছোট, তাই T(n) = Θ(f(n)).

n যখন b-এর ঘাত নয়, তখন ⌊n/b⌋ বা ⌈n/b⌉ নিয়ে একই যুক্তি একটু বেশি হিসাবসহ চলে — CLRS-এ সেই অংশটি আলাদা করে দেখানো আছে, আর ফল বদলায় না।

পুরো সিদ্ধান্ত-প্রক্রিয়াটি f(n) = Θ(n^d log^k n) ধরনের ফাংশনের জন্য ছোট একটি pseudocode-এ লেখা যায়:

MASTER(a, b, d, k)            // T(n) = a T(n/b) + Θ(n^d log^k n), a ≥ 1, b > 1
    e = log_b(a)               // watershed exponent
    if d < e:   return Θ(n^e)                      // case 1
    if d == e:
        if k ≥ 0: return Θ(n^e · log^(k+1) n)      // case 2
        else:     return "gap: master theorem does not apply"
    if d > e:   return Θ(n^d · log^k n)            // case 3 (regularity holds)

৪ · ধাপে ধাপে সিদ্ধান্ত — আটটি recurrence

নিয়ম জানা আর প্রয়োগে দক্ষ হওয়া আলাদা জিনিস। প্রতিটি recurrence-এ একই চার ধাপ: (১) a, b, f চিনুন, (২) watershed n^{log_b a} হিসাব করুন, (৩) f-এর সাথে তুলনা করুন, (৪) case-এর শর্ত মিলিয়ে উত্তর লিখুন। নিচে আটটি recurrence-এ এই চার ধাপ চালানো হলো — শেষটি ইচ্ছা করে একটি ফাঁদ।

a = 1, b = 2, f(n) = 1
watershed : n^(log_2 1) = n^0 = 1
compare   : f(n) = Θ(1) = Θ(n^0 · log^0 n)  ->  equal, k = 0
case 2    : T(n) = Θ(log n)

a = 2, b = 2, f(n) = n
watershed : n^(log_2 2) = n^1
compare   : f(n) = Θ(n)  ->  equal, k = 0
case 2    : T(n) = Θ(n log n)

a = 7, b = 2, f(n) = n^2
watershed : n^(log_2 7) ≈ n^2.807
compare   : n^2 = O(n^(2.807 - 0.8))  ->  smaller, ε ≈ 0.8
case 1    : T(n) = Θ(n^(log_2 7)) ≈ Θ(n^2.81)

a = 3, b = 2, f(n) = n
watershed : n^(log_2 3) ≈ n^1.585
compare   : n = O(n^(1.585 - 0.5))  ->  smaller, ε ≈ 0.5
case 1    : T(n) = Θ(n^(log_2 3)) ≈ Θ(n^1.585)

a = 2, b = 2, f(n) = n log n
watershed : n^1
compare   : n log n = Θ(n · log^1 n)  ->  equal up to log, k = 1
            (NOT polynomially larger: no ε works)
case 2    : T(n) = Θ(n log^2 n)

a = 4, b = 2, f(n) = n^2
watershed : n^(log_2 4) = n^2
compare   : f(n) = Θ(n^2)  ->  equal, k = 0
case 2    : T(n) = Θ(n^2 log n)

a = 1, b = 2, f(n) = n
watershed : n^0 = 1
compare   : n = Ω(n^(0 + 1))  ->  larger, ε = 1
regularity: 1 · f(n/2) = n/2 <= (1/2) · n,  c = 1/2 < 1   OK
case 3    : T(n) = Θ(n)

a = 2, b = 2, f(n) = n / log n
watershed : n^1
case 1?   : n / log n = O(n^(1 - ε)) ?  NO  (n^ε / log n grows)
case 2?   : n / log n = n · log^(-1) n,  k = -1 < 0   NO
case 3?   : f is smaller, not larger      NO
no case   : use recursion tree  ->  Θ(n log log n)

পরীক্ষার হলের শর্টকাট: a বনাম b^d

f(n) = Θ(n^d) হলে log হিসাব না করেই case বলা যায়। d আর log_b a-র তুলনা আসলে b^d আর a-র তুলনা, কারণ b > 1 হলে b^x বাড়ন্ত ফাংশন। তাই:

• a > b^d → case 1, Θ(n^{log_b a}). যেমন 7T(n/2) + n²: 7 > 2² = 4.
• a = b^d → case 2, Θ(n^d log n). যেমন 4T(n/2) + n²: 4 = 2².
• a < b^d → case 3, Θ(n^d). যেমন 2T(n/2) + n²: 2 < 4.

ব্যাখ্যাটাও সুন্দর: a/b^d হলো পাশাপাশি দুই তলার খরচের অনুপাত। প্রতি তলায় নোড a গুণ বাড়ে, আর প্রতিটি নোডের কাজ b^d গুণ কমে। অনুপাত ১-এর বেশি হলে খরচ নিচে গড়ায়, কম হলে ওপরে জমে, সমান হলে সব তলা এক। অংশ ২-এর গাছগুলোতে এই অনুপাত ছিল ½, ১ আর ২।

৫ · আরও উদাহরণ — b = 2 ছাড়াও, আর একটু চালাকি

সব recurrence-এ b = 2 থাকে না, আর f সবসময় পরিচ্ছন্ন n^d হয় না। কয়েকটি ক্লাসিক উদাহরণ হাতে করে দেখি — এগুলো বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় বারবার আসে।

উদাহরণ ১: T(n) = 9T(n/3) + n

a = 9, b = 3, watershed n^{log₃ 9} = n². f = n = O(n²⁻¹), ε = 1. Case 1: T(n) = Θ(n²). গাছে প্রতি তলায় খরচ ৩ গুণ বাড়ে (n, 3n, 9n, …), আর শেষে n²টি পাতা।

উদাহরণ ২: T(n) = T(2n/3) + 1

এখানে b একটি ভগ্নাংশ — n/b = 2n/3 মানে b = 3/2 (যা ১-এর বেশি, তাই চলবে)। a = 1, watershed n^{log_3/2 1} = n⁰ = 1. f = 1 — সমান, k = 0. Case 2: T(n) = Θ(log n). প্রতিবার এক-তৃতীয়াংশ ফেলে দিলেও log-ই থাকে — শুধু log-এর ভিত্তি ৩/২, যা Θ-তে কোনো পার্থক্য করে না।

উদাহরণ ৩: T(n) = 3T(n/4) + n log n

a = 3, b = 4, watershed n^{log₄ 3} ≈ n^0.793. f = n log n = Ω(n^{0.793 + 0.2}) — polynomially বড়, ε ≈ ০.২. Regularity: 3·(n/4)·log(n/4) ≤ (3/4)·n log n, কারণ log(n/4) < log n. তাই c = 3/4 < 1. Case 3: T(n) = Θ(n log n).

উদাহরণ ৪: T(n) = 2T(n/4) + √n

a = 2, b = 4, watershed n^{log₄ 2} = n^1/2 = √n. f = √n — সমান। Case 2: T(n) = Θ(√n log n). ভগ্নাংশ ঘাত দেখে ঘাবড়ানোর কিছু নেই — নিয়ম একই।

উদাহরণ ৫: T(n) = 8T(n/2) + n²

Matrix গুণের সরল divide and conquer: ৮টি অর্ধেক-গুণ। Watershed n^{log₂ 8} = n³, f = n² — case 1, Θ(n³). সাধারণ তিন-লুপের গুণের চেয়ে কোনো লাভ নেই! Strassen ৮-কে ৭ বানিয়ে watershed-টাই নামিয়ে দেন — এখানেই master theorem একটি নকশা-শিক্ষা দেয়: case 1-এ উত্তর ঠিক করে a আর b, f নয়। তাই উন্নতি চাইলে subproblem-এর সংখ্যা কমাতে হবে, জোড়া দেওয়ার কাজ কমিয়ে লাভ নেই।

উদাহরণ ৬: T(n) = 4T(n/2) + n log n

Watershed n², আর f = n log n. log n থাকায় ঘাবড়াবেন না — n log n = O(n^1.5), অর্থাৎ n²-এর চেয়ে n^0.5 গুণক ছোট (log n যেকোনো n^ε-এর চেয়ে ধীরে বাড়ে)। তাই এটি পরিষ্কার case 1: T(n) = Θ(n²). মনে রাখুন, log-এর গুণক কেবল তখনই গুরুত্বপূর্ণ, যখন f আর watershed-এর ঘাত হুবহু সমান — তখন সেটি case 2-এর k ঠিক করে। ঘাত আলাদা হলে log-এর গুণক কোনো case বদলাতে পারে না।

৬ · কখন খাটে না — আর তখন কী করবেন

Master theorem একটি ধারালো ছুরি, কিন্তু সব কিছু কাটে না। প্রথমে দেখি সেই ফাঁদটি — 2T(n/2) + n/log n — গাছ এঁকে নিজেই উত্তর বের করি। ধরি n = 2¹⁶ = 65,536, আর গাছ থামে আকার ২-এ।

nodes at level j : 2^j
size of each     : n / 2^j
cost of each     : (n/2^j) / lg(n/2^j) = (n/2^j) / (16 - j)
level total      : 2^j · (n/2^j) / (16 - j) = n / (16 - j)

level 0 : 65536 / 16 =  4096
level 1 : 65536 / 15 ≈  4369
level 2 : 65536 / 14 ≈  4681
level 3 : 65536 / 13 ≈  5041
... costs grow, but slowly

level 12 : 65536 / 4 = 16384
level 13 : 65536 / 3 ≈ 21845
level 14 : 65536 / 2 = 32768
level 15 : 65536 / 1 = 65536

total = n · (1/16 + 1/15 + ... + 1/2 + 1/1)
      = n · H_16
      ≈ 65536 · 3.3807
      ≈ 221559

n         =    65536
n · H_16  ≈   221559     <- our recurrence
n · lg n  =  1048576

H_m ≈ ln m,  m = lg n   ->   T(n) = Θ(n log log n)

Gap ছাড়াও আরও কয়েকটি পরিস্থিতিতে master theorem সরাসরি প্রয়োগ করা যায় না। পরিস্থিতি দেখেই চিনে ফেলুন:

Regularity শর্ত ভাঙার উদাহরণ দৈনন্দিন অ্যালগরিদমে প্রায় পাওয়াই যায় না, কিন্তু তাত্ত্বিকভাবে আছে: f(n) যদি ওঠানামা করে — কোনো n-এ বিশাল, ঠিক তার অর্ধেকে প্রায় শূন্যের কাছে — তাহলে a·f(n/b) কোনো কোনো n-এ f(n)-কে ছাড়িয়ে যেতে পারে, যদিও গড়ে f “বড়”। তখন তলার খরচ নিয়মিত হারে কমে না, আর case 3-এর যুক্তি দাঁড়ায় না। এজন্যই শর্তটি উপপাদ্যে আলাদা করে লেখা থাকে, যদিও সাধারণ বহুপদী f-এ এটি আপনা-আপনি মেলে।

বিয়োগের recurrence-গুলো দেখতে নিরীহ, কিন্তু ফল একেবারে আলাদা। T(n) = 2T(n/2) + 1 মাত্র Θ(n), অথচ T(n) = 2T(n−1) + 1 হলো Θ(2ⁿ) — Hanoi টাওয়ারের চাল গোনার recurrence (পর্ব ০৭ ও ০৮-এ এটি দেখেছেন)। পার্থক্য গভীরতায়: ভাগ করলে গাছ log n তলা নামে, বিয়োগ করলে n তলা। দুই ক্ষেত্রেই প্রতি তলায় নোড দ্বিগুণ হয়, কিন্তু log n তলায় সেটা মাত্র n টি পাতা, আর n তলায় 2ⁿটি। তাই কোডে f(n-1) দুবার ডাকা দেখলেই সতর্ক হোন — সাধারণত সেটি exponential, আর সমাধান প্রায়ই memoization (পর্ব ৫২)।

শেষ সারির কৌশলটির নাম চলক বদল (change of variables): n = 2^m ধরলে √n = 2^m/2, আর S(m) = T(2^m) লিখলে recurrence হয়ে যায় S(m) = 2S(m/2) + m — যা merge sort-এর চেনা রূপ। সমাধান করে m-এর জায়গায় lg n ফেরত বসালেই কাজ শেষ। অচেনা recurrence-কে চেনা ছাঁচে টেনে আনার এই চিন্তাটা master theorem-এর চেয়েও বেশি কাজের।

৭ · নিজে হিসাব করুন — Master theorem calculator

নিচের ছোট টুলটিতে a, b আর f(n) = n^d log^k n-এর d ও k বসান — সাথে সাথে case আর উত্তর দেখাবে। “চালান” চাপলে ওপরে ঘরগুলো আসবে, আর নিচের আউটপুটে অংশ ৪-এর আটটি recurrence-এর ফল ছাপা হবে। ঘরের মান বদলে নিজের recurrence পরীক্ষা করুন — যেমন Strassen-এর জন্য a = 7, b = 2, d = 2, k = 0.

// T(n) = a*T(n/b) + f(n),  f(n) = n^d * (log n)^k
function master(a, b, d, k) {
  if (!(a >= 1 && b > 1)) return 'not applicable: need a >= 1 and b > 1';
  const e = Math.log(a) / Math.log(b);                 // watershed exponent log_b a
  const pw = (x) => (x === 0 ? '' : x === 1 ? 'n' : `n^${+x.toFixed(3)}`);
  const lg = (p) => (p === 0 ? '' : p === 1 ? 'log n' : `log^${p} n`);
  const th = (...t) => `Theta(${t.filter(Boolean).join(' ') || '1'})`;
  const E = Math.abs(e - Math.round(e)) < 1e-9 ? Math.round(e) : e;
  if (Math.abs(d - e) < 1e-9) {                        // f equals the watershed (up to logs)
    if (k >= 0) return `case 2 -> ${th(pw(E), lg(k + 1))}`;
    return `gap, k < 0 (use recursion tree) -> ${th(pw(E), k === -1 ? 'log log n' : '')}`;
  }
  if (d < e) return `case 1, smaller by n^${+(e - d).toFixed(3)} -> ${th(pw(E))}`;
  return `case 3, a/b^d = ${+(a / b ** d).toFixed(3)} < 1 -> ${th(pw(d), lg(k))}`;
}
const ids = ['a', 'b', 'd', 'k'];
function show() {
  const [a, b, d, k] = ids.map((x) => Number(document.getElementById(x).value));
  document.getElementById('res').textContent = master(a, b, d, k);
}
ids.forEach((x) => { document.getElementById(x).oninput = show; });
show();
for (const [a, b, d, k] of [[1, 2, 0, 0], [2, 2, 1, 0], [7, 2, 2, 0], [3, 2, 1, 0],
                            [2, 2, 1, 1], [4, 2, 2, 0], [1, 2, 1, 0], [2, 2, 1, -1]])
  console.log(`a=${a} b=${b} d=${d} k=${k}: ${master(a, b, d, k)}`);

টুলটি দিয়ে কয়েকটি পরীক্ষা নিজে করে দেখুন। (১) a = 1, b = 1.5, d = 0, k = 0 বসান — এটি অংশ ৫-এর T(2n/3) + 1, উত্তর আসবে Θ(log n). (২) a = 3, b = 4, d = 1, k = 1 — উদাহরণ ৩-এর case 3, সাথে অনুপাত a/b^d = 0.75, যা regularity-র c. (৩) a = 2, b = 4, d = 0.5 — √n-এর উদাহরণ, case 2. (৪) a = 0.5 বসালে টুলটি নিজেই জানাবে যে উপপাদ্য প্রযোজ্য নয়। (৫) শেষে a = 8, b = 2, d = 2 আর a = 7, b = 2, d = 2 পাশাপাশি চালান — Strassen-এর একটি গুণ বাঁচানো ঘাতকে ৩ থেকে ২.৮০৭-এ নামায়। টুলটি শুধু হিসাব মেলানোর সহায়ক; পরীক্ষার খাতায় ধাপগুলো নিজের হাতে লিখতে হবে।

৮ · সংখ্যায় যাচাই — ভবিষ্যদ্বাণী কি সত্যি মেলে?

সূত্র যা বলছে, কম্পিউটার কি তা মানে? যাচাইয়ের সহজ উপায়: n = 2ⁱ নিয়ে recurrence-টি সরাসরি হিসাব করুন (T(1) = 1), তারপর ভাগ করুন ভবিষ্যদ্বাণী করা ফাংশন দিয়ে। Θ সঠিক হলে n বাড়ার সাথে অনুপাতটি একটি ধ্রুবকের কাছে থিতু হবে — শূন্যের দিকেও যাবে না, অসীমের দিকেও না। নিচে তিনটি recurrence, তিন case থেকে একটি করে:

• merge: 2T(n/2) + n, ভবিষ্যদ্বাণী Θ(n lg n) — case 2
• karatsuba: 3T(n/2) + n, ভবিষ্যদ্বাণী Θ(n^{lg 3}) = Θ(3ⁱ) — case 1
• halving: T(n/2) + n, ভবিষ্যদ্বাণী Θ(n) — case 3

#include <cstdio>
#include <initializer_list>

// T(1) = 1,  T(n) = a*T(n/2) + n^p,  n = 2^i  (exact integers)
long long solve(long long a, int p, int i) {
    long long t = 1;
    for (int j = 1; j <= i; ++j) {
        long long f = 1;
        for (int e = 0; e < p; ++e) f *= (1LL << j);
        t = a * t + f;
    }
    return t;
}

int main() {
    std::printf("%4s %10s %10s %10s\n", "i", "merge", "karatsuba", "halving");
    for (int i : {4, 8, 12, 16, 20}) {
        double n = double(1LL << i), p3 = 1;
        for (int j = 0; j < i; ++j) p3 *= 3;             // n^(log2 3) = 3^i
        double m = solve(2, 1, i) / (n * i);             // vs n log2 n
        double k = solve(3, 1, i) / p3;                  // vs n^1.585
        double h = solve(1, 1, i) / n;                   // vs n
        std::printf("%4d %10.4f %10.4f %10.4f\n", i, m, k, h);
    }
}

# T(1) = 1,  T(n) = a*T(n/2) + n^p,  n = 2^i  (exact integers)
def solve(a, p, i):
    t = 1
    for j in range(1, i + 1):
        t = a * t + (2 ** j) ** p
    return t

print(f"{'i':>4} {'merge':>10} {'karatsuba':>10} {'halving':>10}")
for i in (4, 8, 12, 16, 20):
    n = 2 ** i
    m = solve(2, 1, i) / (n * i)      # vs n log2 n
    k = solve(3, 1, i) / 3 ** i       # vs n^(log2 3) = 3^i
    h = solve(1, 1, i) / n            # vs n
    print(f"{i:4d} {m:10.4f} {k:10.4f} {h:10.4f}")

   i      merge  karatsuba    halving
   4     1.2500     2.6049     1.9375
   8     1.1250     2.9220     1.9961
  12     1.0833     2.9846     1.9998
  16     1.0625     2.9970     2.0000
  20     1.0500     2.9994     2.0000

সময় তো হলো — জায়গা কত?

Master theorem শুধু সময় বলে। রিকার্সিভ অ্যালগরিদমের জায়গা (space) আলাদা করে ভাবতে হয়, আর এখানে মূল প্রশ্ন দুটি: একসাথে call stack-এ সর্বোচ্চ কয়টি ডাক থাকে (গভীরতা), আর প্রতিটি ডাক কত বাড়তি মেমরি নেয়। Merge sort-এ গভীরতা Θ(log n), কিন্তু merge-এর জন্য Θ(n) আকারের অস্থায়ী array লাগে — মোট বাড়তি জায়গা Θ(n). রিকার্সিভ binary search-এ প্রতিটি ডাক Θ(1) জায়গা নেয়, গভীরতা Θ(log n), তাই জায়গা Θ(log n); লুপ দিয়ে লিখলে Θ(1). Karatsuba-তে প্রতিটি তলায় অস্থায়ী সংখ্যা রাখতে হয়, যার যোগফল n + n/2 + n/4 + … = Θ(n). লক্ষ করুন — সময়ের গাছে সব নোড যোগ হয়, কিন্তু জায়গার হিসাবে শুধু মূল থেকে একটি পাতা পর্যন্ত একটি পথ, কারণ একই সময়ে কেবল সেই পথের ডাকগুলোই জীবিত থাকে।

৯ · AI-এর যুগে master theorem

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

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

• কোড দেখে নিজে recurrence লিখেছি, আর AI-এর recurrence-এর সাথে মিলিয়েছি — ডাকের সংখ্যা আর আকার দুটোই
• a ≥ 1 ধ্রুবক, b > 1 ধ্রুবক, আর আকার ভাগ হচ্ছে (বিয়োগ নয়) — তিনটিই নিশ্চিত করেছি
• “ছোট” বা “বড়” বলার আগে polynomial ব্যবধান (n^ε) সত্যিই আছে কি না দেখেছি
• Case 3 হলে regularity-র c < 1 নিজে বের করেছি
• ছোট n-এ recursion tree এঁকে অন্তত দুই তলার খরচ হাতে হিসাব করেছি
• বড় n-এ T(n)/ভবিষ্যদ্বাণী অনুপাত চালিয়ে দেখেছি যে এটি একটি ধ্রুবকে থিতু হয়