মাস্টার থিওরেম

১ · মাস্টার থিওরেম — বিবৃতি

মাস্টার থিওরেমMaster Theoremএকটি নির্দিষ্ট আকৃতির (aT(n/b)+f(n)) রিকারেন্সের অ্যাসিম্পটোটিক সমাধান সরাসরি বলে দেওয়ার একটি সুত্র, যা f(n)-কে n^(log_b a)-এর সাথে তুলনা করে তিনটি case-এ ভাগ করে। ধরা যাক $a \ge 1$ এবং $b > 1$ ধ্রুবক, এবং $f(n)$ একটি অ্যাসিম্পটোটিকভাবে ধনাত্মক ফাংশন। তাহলে নিচের রিকারেন্সের সমাধান (যেখানে $n/b$-কে $\lfloor n/b \rfloor$ বা $\lceil n/b \rceil$ ধরা হয় — এই টেকনিক্যাল পার্থক্য অ্যাসিম্পটোটিক ফলাফল পরিবর্তন করে না):

$$T(n) = aT(n/b) + f(n)$$

নির্ভর করে $f(n)$-কে "ওয়াটারশেড" ফাংশন $n^{\log_b a}$-এর সাথে কীভাবে তুলনা করা যায়, তার উপর — এই মান হলো, স্বজ্ঞাতভাবে, গাছের লিফ সংখ্যা (L12-এর রিকার্সন ট্রির ভাষায়, যদি প্রতিটি লিফের খরচ $\Theta(1)$ হতো)।

২ · তিনটি জেনুইন সংখ্যাগত উদাহরণ — এক case, এক উদাহরণ

Case ১ · $T(n) = 8T(n/2) + n^2$

এখানে $a=8,\ b=2$, তাই $n^{\log_b a} = n^{\log_2 8} = n^3$। আর $f(n)=n^2$। প্রশ্ন: $n^2$ কি $n^3$-এর চেয়ে পলিনমিয়ালি ছোট? হ্যাঁ — $\epsilon=1$ নিলে $n^2 = O(n^{3-1}) = O(n^2)$ ✓। সুতরাং case ১ প্রযোজ্য:

$$T(n) = \Theta(n^3)$$

(লক্ষ্য করুন — এটি ঠিক ন্যায়ভ, "ট্রিক ছাড়া" ডিভাইড অ্যান্ড কনকার ম্যাট্রিক্স গুণনের রিকারেন্স, যেখানে $2\times2$ ব্লক গুণনে $8$টি রিকার্সিভ গুণন লাগে — ফলাফল সাধারণ $O(n^3)$ ইটারেটিভ পদ্ধতির সমান। L18-এ দেখা যাবে স্ট্রাসেনের চতুর কৌশল ঠিক এই $a=8$-কে $a=7$-এ নামিয়ে আনে, যা $\Theta(n^{\log_2 7})\approx\Theta(n^{2.807})$ দেয় — এই একই কেস-১ যুক্তি দিয়েই।)

Case ২ · $T(n) = 2T(n/2) + n$

এখানে $a=2,\ b=2$, তাই $n^{\log_b a} = n^{\log_2 2} = n^1 = n$। আর $f(n) = n = \Theta(n^1 \cdot \log^0 n)$, অর্থাৎ $k=0$। সুতরাং case ২ প্রযোজ্য:

$$T(n) = \Theta(n^1 \log^{0+1} n) = \Theta(n\log n)$$

এটি ঠিক L11-এ সাবস্টিটিউশন মেথড দিয়ে যা প্রমাণ করা হয়েছিল, তার সাথে হুবহু মিলে যায় — কিন্তু এবার কোনো ইনডাকশন বা রিকার্সন ট্রি না এঁকেই, শুধু $a, b, f(n)$ বসিয়েই উত্তর পাওয়া গেল। এটাই এই রিকারেন্সটি, যা L15-এ মার্জ সর্টের বিশ্লেষণেও হুবহু আবার দেখা যাবে।

Case ৩ · $T(n) = 2T(n/2) + n^2$

লক্ষ্য করুন — এটি ঠিক L12-এর রিকার্সন ট্রি উদাহরণ! এখানে $a=2,\ b=2$, তাই $n^{\log_b a} = n^1 = n$। আর $f(n)=n^2$। প্রশ্ন: $n^2$ কি $n$-এর চেয়ে পলিনমিয়ালি বড়? হ্যাঁ — $\epsilon=1$ নিলে $n^2 = \Omega(n^{1+1})$ ✓। কিন্তু case ৩ প্রয়োগ করার আগে রেগুলারিটি কন্ডিশন যাচাই করতে হবে — এটাই একমাত্র case যেখানে একটি বাড়তি শর্ত লাগে:

$$a\,f(n/b) \le c\,f(n) \quad \text{কোনো ধ্রুবক } c<1 \text{-এর জন্য}$$

এখানে $a f(n/b) = 2 \cdot (n/2)^2 = 2 \cdot n^2/4 = n^2/2 = 0.5 \cdot f(n)$ — অর্থাৎ $c=0.5<1$ দিয়ে শর্তটি সন্তুষ্ট হয় ✓। (স্বজ্ঞাতভাবে: রেগুলারিটি কন্ডিশন নিশ্চিত করে যে রুটের নিজস্ব খরচ প্রতিটি পুনরাবৃত্তিতে "যথেষ্ট দ্রুত" কমছে যেন উপ-সমস্যাগুলোর মোট খরচ কখনো রুটের খরচকে ছাড়িয়ে না যায় — L12-এর জ্যামিতিক-সিরিজ যুক্তিরই একটি আনুষ্ঠানিক রূপ।) উভয় শর্ত পূরণ হওয়ায় case ৩ প্রযোজ্য:

$$T(n) = \Theta(f(n)) = \Theta(n^2)$$

এটি ঠিক L12-এ রিকার্সন ট্রি এঁকে যে ফলাফল পাওয়া গিয়েছিল (এবং কোড দিয়ে $T(n)/n^2 \to 2$ পরীক্ষামূলকভাবে যাচাই করা হয়েছিল), তার সাথে হুবহু মেলে — তিনটি ভিন্ন পদ্ধতি (রিকার্সন ট্রি, সরাসরি গণনা, এবং এখন মাস্টার থিওরেম) একই সিদ্ধান্তে পৌঁছেছে।

৩ · সত্যিকারের কোড — Case ২-এর বাউন্ড যাচাই

যেহেতু case ২-এর $T(n)=2T(n/2)+n$ রিকারেন্সটি M4-এ মার্জ সর্টের বিশ্লেষণে সরাসরি ব্যবহৃত হবে, চলুন এটিকেই পরীক্ষামূলকভাবে যাচাই করি — কিন্তু এবার ভিন্ন একটি কোণ থেকে: $T(n)/(n\log_2 n)$ অনুপাতের বদলে, $n$ দ্বিগুণ হলে $T(n)$ কত গুণ বাড়ে তা দেখব। যদি $T(n)$ প্রকৃতপক্ষে $\Theta(n)$ হতো (কোনো log ফ্যাক্টর ছাড়াই), তাহলে $n$ দ্বিগুণ হলে $T(n)$ও ঠিক দ্বিগুণ হতো। কিন্তু case ২ বলছে এখানে একটি বাড়তি $\log n$ ফ্যাক্টর আছে — তাই অনুপাতটা $2$-এর চেয়ে সামান্য বেশি হওয়ার কথা, এবং $n$ বাড়ার সাথে সাথে ধীরে ধীরে $2$-এর দিকে নামতে থাকার কথা।

def T(n):
    if n <= 1:
        return 1                 # বেস কেস T(1) = 1
    return 2 * T(n // 2) + n     # case ২-এর রিকারেন্স

sizes = [8, 16, 32, 64, 128, 256]
values = [(n, T(n)) for n in sizes]

print(f"{'n':>5} | {'T(n)':>8}")
for n, t in values:
    print(f"{n:>5} | {t:>8}")

print("\nn দ্বিগুণ হলে T(n) কত গুণ বাড়ে (T(2n)/T(n)):")
for i in range(1, len(values)):
    n_prev, t_prev = values[i - 1]
    n_cur, t_cur = values[i]
    ratio = t_cur / t_prev
    print(f"n={n_prev}->{n_cur}: {ratio:.4f}x  (বিশুদ্ধ Θ(n) হলে ঠিক 2.0000x হতো)")

৪ · মাস্টার থিওরেমের সীমাবদ্ধতা

মাস্টার থিওরেম শক্তিশালী কিন্তু সর্বজনীন নয়। এটি প্রযোজ্য হয় না যদি:

• উপসমস্যাগুলো অসম আকারের হয় (যেমন $T(n) = T(n/3) + T(2n/3) + n$) — এখানে "একক $a,b$" ধরে নেওয়া যায় না।
• $f(n)$ কোনো case-এর সাথেই ঠিক মেলে না — একে "ফাঁক" (gap) বলা হয়। যেমন $T(n) = 2T(n/2) + n/\log n$: এখানে $n^{\log_2 2}=n$, আর $f(n)=n/\log n$ হলো $n$-এর চেয়ে সামান্য ছোট, কিন্তু কোনো পলিনমিয়াল ফ্যাক্টর ($n^\epsilon$) দিয়ে ছোট নয় (শুধু একটি $\log$ ফ্যাক্টর দিয়ে) — case ১ এর শর্ত পূরণ হয় না, আবার এটি case ২-এর $\Theta(n\log^k n)$ ফর্মেও নেই ($k$ ঋণাত্মক হতে হতো)। এমন ক্ষেত্রে মাস্টার থিওরেম "উত্তর নেই" বলে দেয় — সাবস্টিটিউশন বা আরও উন্নত টুল (যেমন Akra-Bazzi পদ্ধতি) লাগবে।
• case ৩-এ রেগুলারিটি কন্ডিশন সত্য না হয় — যদিও $f(n)$ পলিনমিয়ালি বড়, তবু বাউন্ড $\Theta(f(n))$ নাও হতে পারে যদি $f(n)$ অতিরিক্ত "অনিয়মিত" হয় (ব্যবহারিক ক্ষেত্রে এই শর্ত ভাঙা বিরল, কিন্তু আনুষ্ঠানিক প্রমাণে এটি উল্লেখ করা আবশ্যক)।