সাবস্টিটিউশন মেথড

The substitution method

১৩ মিনিট পড়া মধ্যম-কঠিন · Intermediate-Advanced Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

সাবস্টিটিউশন মেথড দুটো ধাপে চলে — (১) একটি বাউন্ড অনুমান করো, (২) গাণিতিক ইনডাকশন দিয়ে সেই অনুমান প্রমাণ করো, রিকারেন্সের মধ্যে অনুমানটি "প্রতিস্থাপন" (substitute) করে।
উদাহরণ: $T(n) = 2T(n/2) + n$-এর জন্য আমরা অনুমান করি $T(n) = O(n\log n)$, তারপর দেখাই এই অনুমান রিকারেন্সের নিজের শর্ত পূরণ করে।
একটি সূক্ষ্ম কিন্তু গুরুত্বপূর্ণ ফাঁদ আছে — বেস কেস n=1-এ সরাসরি যাচাই করলে অনুমানটি ব্যর্থ হয় ($\log 1 = 0$)। রিগোরাস প্রমাণে এই সমস্যা এড়াতে হয় ভিন্নভাবে বেস কেস বেছে নিয়ে।
নিচের কোড সেলে সত্যিকারের Python দিয়ে $T(n)/(n\log_2 n)$ অনুপাত গণনা করে দেখানো হয়েছে এটি ঠিক $1$-এর দিকে এগিয়ে যায় — প্রমাণের সাথে সরাসরি মিলে যায়।

এই পাঠে যা শিখবেন

সাবস্টিটিউশন মেথডের দুটি ধাপ — অনুমান করা ও ইনডাকশন দিয়ে প্রমাণ করা
$T(n) = 2T(n/2) + n$-এর জন্য সম্পূর্ণ, রিগোরাস ইনডাক্টিভ প্রমাণ, ধাপে ধাপে
বেস কেস নিয়ে ক্লাসিক ফাঁদ — কেন $n_0=1$ কাজ করে না এবং $n_0=2$ বেছে নেওয়া কেন সমস্যার সমাধান করে
প্রমাণিত বাউন্ড সত্যিকারের কোড দিয়ে পরীক্ষামূলকভাবে যাচাই করা

১ · সাবস্টিটিউশন মেথড — ধারণা

সাবস্টিটিউশন মেথডSubstitution Methodএকটি রিকারেন্সের সমাধান অনুমান করে, সেই অনুমানকে রিকারেন্সের মধ্যে প্রতিস্থাপন করে গাণিতিক ইনডাকশন দিয়ে প্রমাণ করার পদ্ধতি। L10-এ আমরা দেখেছি একটি রিকার্সিভ অ্যালগরিদমের কল-কাউন্ট রিকারেন্স থাকে। কিন্তু সেই রিকারেন্সের বন্ধ-আকারের (closed-form) সমাধান — অর্থাৎ এটি ঠিক কোন অ্যাসিম্পটোটিক ক্লাসের অন্তর্ভুক্ত — তা বের করার সবচেয়ে সাধারণ পদ্ধতি হলো সাবস্টিটিউশন মেথড, যার দুটো ধাপ:

দুটো ধাপ (অনুমান + ইনডাকশন) — কিন্তু ইনডাকশনের ভেতরে বেস কেস আলাদাভাবে যাচাই করাটা প্রায়ই সবচেয়ে সূক্ষ্ম অংশ, নিচে দেখুন।

ধাপ ১ · অনুমান
রিকারেন্সের গঠন দেখে (বা রিকার্সন ট্রি স্কেচ করে — পরের পাঠ L12) একটি সম্ভাব্য অ্যাসিম্পটোটিক বাউন্ড অনুমান করো, একটি অজানা ধ্রুবক $c$ সহ।

ধাপ ২ · ইনডাকশন
ধরে নাও অনুমানটি সব ছোট মানের জন্য সত্য (ইনডাক্টিভ হাইপোথিসিস), তারপর দেখাও এটি রিকারেন্সে প্রতিস্থাপন করলে $n$-এর জন্যও সত্য থাকে — উপযুক্ত $c$ বেছে নিয়ে।

২ · সম্পূর্ণ উদাহরণ — $T(n) = 2T(n/2) + n$

এই রিকারেন্সটি খুবই পরিচিত — এটি L15-এ মার্জ সর্টের অ্যানালাইসিসেও ঠিক এভাবেই দেখা যাবে। আমরা অনুমান করি $T(n) = O(n \log n)$, অর্থাৎ কোনো ধ্রুবক $c > 0$ এবং $n_0$ আছে যেন সব $n \ge n_0$-এর জন্য:

$$T(n) \le c \, n \log_2 n$$

ইনডাক্টিভ হাইপোথিসিস: ধরে নিই এই বাউন্ড সব ছোট মানের জন্য সত্য — বিশেষত $T(n/2) \le c \, (n/2) \log_2(n/2)$। এবার এটি মূল রিকারেন্সে প্রতিস্থাপন করি:

$$T(n) = 2T(n/2) + n \le 2\Big[c\,\frac{n}{2}\log_2\frac{n}{2}\Big] + n = c\,n\,(\log_2 n - 1) + n$$

$$= c\,n\log_2 n - c\,n + n = c\,n\log_2 n - n(c - 1)$$

আমাদের লক্ষ্য ছিল $T(n) \le c\,n\log_2 n$ দেখানো — উপরের সমীকরণে দেখা যাচ্ছে এটি সত্যি হবে যদি $n(c-1) \ge 0$, অর্থাৎ যেকোনো ধ্রুবক $c \ge 1$ বেছে নিলেই ইনডাক্টিভ ধাপটি কাজ করে। এখানেই সাবস্টিটিউশনের "প্রতিস্থাপন" অংশটি সম্পন্ন — অনুমানটি রিকারেন্সের নিজের শর্ত পূরণ করে দেখিয়েছি।

সূক্ষ্ম ফাঁদ — বেস কেস কেন n=1-এ যাচাই করা যায় না

স্বাভাবিকভাবেই মনে হতে পারে যে এবার শুধু $T(1)$-এ বাউন্ডটি যাচাই করলেই প্রমাণ শেষ। কিন্তু $\log_2 1 = 0$, তাই ডানপাশ $c \cdot 1 \cdot 0 = 0$ — অথচ $T(1) = \Theta(1) > 0$। অর্থাৎ $n_0 = 1$ বেস কেস হিসেবে বেছে নিলে বাউন্ডটি ব্যর্থ হয়! এটি সাবস্টিটিউশন মেথডের একটি সুপরিচিত, প্রায়ই ভুলে যাওয়া সূক্ষ্মতা। সমাধান: বেস কেস হিসেবে $n_0 = 2$ বেছে নাও এবং strong induction ব্যবহার করো (অর্থাৎ ধরে নাও বাউন্ডটি $n$-এর চেয়ে ছোট সব মানের জন্য সত্য, শুধু $n/2$-এর জন্য নয়) — এতে $n=2, 3$-এর জন্য সরাসরি যাচাই করলেই যথেষ্ট, আর $n \ge 4$-এর জন্য উপরের ইনডাক্টিভ ধাপ কাজ করে। ধরি $T(1) = 1$: তাহলে $T(2) = 2T(1)+2 = 4$ এবং $T(3) = 2T(1)+3 = 5$ (যেহেতু $\lfloor 3/2 \rfloor = 1$)। $c=2$ বেছে নিলে: $n=2$-এ $c\,n\log_2 n = 2\cdot2\cdot1=4 \ge T(2)=4$ ✓, এবং $n=3$-এ $c\,n\log_2 n = 2\cdot3\cdot1.585 \approx 9.51 \ge T(3)=5$ ✓ — উভয় বেস কেসই $c=2$ দিয়ে সন্তুষ্ট হয়। সুতরাং $c=2,\ n_0=2$ বেছে নিয়ে সম্পূর্ণ প্রমাণ দাঁড়ায়: $T(n) = O(n\log n)$। (নিম্ন বাউন্ড $\Omega(n\log n)$ একইভাবে, ভিন্ন একটি ছোট ধ্রুবক দিয়ে প্রমাণযোগ্য — একসাথে $T(n) = \Theta(n\log n)$।)

৩ · সত্যিকারের কোড — অনুপাত পরীক্ষা করা

এবার প্রমাণটি সত্যিকারের কোড দিয়ে পরীক্ষামূলকভাবে যাচাই করি। নিচের কোড রিকারেন্সের অপারেশন-কাউন্ট সরাসরি রিকার্সনের মাধ্যমে গণনা করে (কোনো বন্ধ-আকারের সূত্র ব্যবহার না করেই), তারপর $T(n)/(n\log_2 n)$ অনুপাত মাপে। Pyodide-এ রিকার্সন-গভীরতার সমস্যা এড়াতে আমরা ছোট, ২-এর ঘাত আকারের $n$ ব্যবহার করছি যাতে n // 2 সবসময় পরিষ্কার পূর্ণসংখ্যা থাকে।

Python

import math

def T(n):
    if n <= 1:
        return 1                    # বেস কেস T(1) = 1
    return 2 * T(n // 2) + n        # রিকারেন্স নিজেই -- কোনো সূত্র অনুমান নয়

sizes = [2, 4, 8, 16, 32, 64, 128, 256]

print(f"{'n':>5} | {'T(n)':>8} | {'n*log2(n)':>10} | {'T(n)/(n*log2(n))':>18}")
for n in sizes:
    t = T(n)
    denom = n * math.log2(n)
    ratio = t / denom
    print(f"{n:>5} | {t:>8} | {denom:>10.2f} | {ratio:>18.4f}")

আউটপুটে দেখা যাবে $T(n)$-এর মান ঠিক $4, 12, 32, 80, 192, 448, 1024, 2304$ — এবং অনুপাত $T(n)/(n\log_2 n)$ ক্রমাগত কমতে থাকে: $2.0,\ 1.5,\ 1.333,\ 1.25,\ 1.2,\ 1.167,\ 1.143,\ 1.125$ — অর্থাৎ এটি $1$-এর দিকে এগিয়ে যাচ্ছে, কখনো এটি অতিক্রম করছে না। এটা প্রত্যাশিতই, কারণ $T(1)=1$ বেস কেসের জন্য এই রিকারেন্সের সঠিক বদ্ধ-আকারের সমাধান হলো ঠিক $T(n) = n\log_2 n + n$ (নিজেই যাচাই করুন: $n=256$-এ $256\times8 + 256 = 2304$, যা কোডের আউটপুটের সাথে হুবহু মেলে)। যেহেতু $T(n)/(n\log_2 n) = 1 + 1/\log_2 n \to 1$, তাই এই অনুপাত কখনোই $1$-এর নিচে নামবে না বা $c=2$-এর প্রমাণিত বাউন্ডকেও অতিক্রম করবে না — অ্যালগরিদমটি সত্যিই $\Theta(n\log n)$, এবং প্রমাণে ব্যবহৃত $c=2$ একটি যথেষ্ট (sufficient) কিন্তু টাইট-সম্ভাব্য-সর্বনিম্ন নয় এমন ধ্রুবক — প্রমাণের লক্ষ্যই থাকে এমন একটি ধ্রুবক খুঁজে বের করা যা কাজ করে, একেবারে সবচেয়ে ছোট ধ্রুবকটি খোঁজা নয়।

মূল কথা · Key takeaway

সাবস্টিটিউশন মেথড রিগোরাস — এটি একটি অনুমানকে ইনডাকশন দিয়ে প্রমাণ করে, অনুমান করে না যে "মনে হচ্ছে ঠিক আছে"। কিন্তু এর একটি দুর্বলতা আছে: প্রথমে একটি ভালো অনুমান লাগবে, যা প্রায়ই রিকারেন্সের গঠন থেকে সরাসরি স্পষ্ট নয়। পরের পাঠ (L12) — রিকার্সন ট্রি মেথড — ঠিক এই অনুমানটি তৈরি করার একটি ভিজ্যুয়াল টুল দেয়, যা প্রায়ই সাবস্টিটিউশনের আগে ব্যবহার করা হয়। আর L13-এর মাস্টার থিওরেম এই দুটোকেই একটি রেডিমেড "কুকবুক"-এ প্যাকেজ করে দেয়, যখন রিকারেন্সটি একটি নির্দিষ্ট গঠন মেনে চলে।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ যদি আমরা ভুল অনুমান করতাম — ধরুন $T(n) = O(n)$ — তাহলে ইনডাক্টিভ ধাপে কী ঘটত?

অনুমান হতো $T(n) \le c\,n$। প্রতিস্থাপন করলে: $T(n) = 2T(n/2)+n \le 2[c\,n/2]+n = cn+n = cn + n$। লক্ষ্য ছিল $T(n) \le cn$ দেখানো, কিন্তু পাওয়া গেল $cn+n$ — যা $cn$-এর চেয়ে বড় (যেহেতু $n>0$), যেকোনো ধ্রুবক $c$-এর জন্যই। ইনডাক্টিভ ধাপ ব্যর্থ হয় — এটাই সংকেত দেয় যে অনুমানটি ভুল (খুব টাইট), এবং একটি বড় ফাংশন (যেমন $n\log n$) অনুমান করে আবার চেষ্টা করতে হবে।

প্র ০২ উপরের প্রমাণে আমরা শুধু $T(n) = O(n\log n)$ (উপরের বাউন্ড) দেখিয়েছি। $\Theta(n\log n)$ বলার জন্য আর কী দরকার?

$\Theta$ বলতে বোঝায় $O$ (উপরের বাউন্ড) এবং $\Omega$ (নিচের বাউন্ড) — দুটোই একসাথে সত্য। নিচের বাউন্ড $T(n) = \Omega(n\log n)$ প্রমাণ করতে একই সাবস্টিটিউশন কৌশল ব্যবহার করা হয়, শুধু অসমতার দিক উল্টে ($T(n) \ge c'\,n\log n$ দেখাতে হয়, ছোট একটি ধ্রুবক $c'$-এর জন্য)। দুটো প্রমাণ একসাথে থাকলেই $T(n)=\Theta(n\log n)$ সম্পূর্ণভাবে প্রতিষ্ঠিত হয় — এই কোর্সে যেখানেই "$\Theta$" বলা হয়েছে, ধরে নিতে হবে উভয় দিকই (নীতিগতভাবে) প্রমাণযোগ্য।

প্র ০৩ কোড সেলে T(1) = 1 বেস কেস ব্যবহার করা হয়েছে, কিন্তু প্রমাণে আমরা $n_0=2$ থেকে ইনডাকশন শুরু করেছি। এই দুটো কি একে অপরের সাথে সাংঘর্ষিক?

না, এরা ভিন্ন জিনিস বোঝায়। কোডের T(1)=1 হলো রিকারেন্সের নিজস্ব সংজ্ঞার বেস কেস (রিকারেন্সটি কীভাবে গণনা করতে হবে, তা বলে)। প্রমাণের $n_0=2$ হলো ইনডাকশনের শুরুর বিন্দু (বাউন্ড $T(n)\le cn\log_2 n$ কোন $n$ থেকে সত্য বলে দাবি করা হচ্ছে, তা বলে)। রিকারেন্স নিজে $n=1$ থেকেই সংজ্ঞায়িত থাকতে পারে, অথচ তার অ্যাসিম্পটোটিক বাউন্ডের প্রমাণটি $n=2$ থেকে শুরু হতে পারে — কারণ অ্যাসিম্পটোটিক বাউন্ড (O/Θ-নোটেশন) এমনিতেই শুধুমাত্র "যথেষ্ট বড়" $n$-এর জন্য সত্য হলেই যথেষ্ট (L06 মনে করুন)।

অনুশীলন

চিন্তা করুন: $T(n) = 2T(n/2) + n$-এর জন্য যদি কেউ অনুমান করে $T(n) \le c\,n\log_2 n - n$ (আগের প্রমাণের চেয়ে সামান্য টাইট একটি বাউন্ড), তাহলে ইনডাক্টিভ ধাপ কি সফল হবে? প্রতিস্থাপন করে দেখুন।

প্রতিস্থাপন করলে: $T(n) \le 2[c(n/2)\log_2(n/2) - n/2] + n = cn\log_2 n - cn - n + n = cn\log_2 n - cn$। লক্ষ্য ছিল $T(n) \le cn\log_2 n - n$ দেখানো। পাওয়া গেল $cn\log_2 n - cn$, যা $cn\log_2 n - n$-এর চেয়ে ছোট বা সমান হবে যদি $cn \ge n$, অর্থাৎ $c \ge 1$ হলেই যথেষ্ট — তাই এই টাইটার অনুমানও কাজ করে! এটা দেখায় সাবস্টিটিউশন মেথডে প্রায়ই একাধিক সঠিক অনুমান/ধ্রুবক থাকতে পারে।
পরীক্ষা করুন: উপরের কোড সেলে রিকারেন্সটি পরিবর্তন করে T(n) = 3 * T(n // 2) + n করুন (একই sizes ব্যবহার করে) এবং দেখুন $T(n)/(n\log_2 n)$ অনুপাত কী রকম আচরণ করে — এটি কি এখনও একটি ধ্রুবকের দিকে এগোয়, নাকি বেড়েই চলে?

এই নতুন রিকারেন্সে $a=3, b=2$, তাই $n^{\log_2 3} \approx n^{1.585}$ — এটি $n\log n$-এর চেয়ে দ্রুত বাড়ে। ফলে $T(n)/(n\log_2 n)$ অনুপাত কোনো ধ্রুবকের দিকে না গিয়ে ক্রমাগত বেড়েই চলবে — এটি সংকেত দেয় যে $T(n) = 3T(n/2)+n$ আসলে $\Theta(n\log n)$ নয়, বরং $\Theta(n^{\log_2 3})$। L13-এর মাস্টার থিওরেম দিয়ে এটি তাৎক্ষণিকভাবে নিশ্চিত করা যাবে (এটি কেস ১-এর একটি উদাহরণ)।