এখানে আমরা দেখব কিভাবে সাবস্টিটিউশন মেথড ব্যবহার করে রিকারেন্স রিলেশন সমাধান করা যায়। আমরা দুটি উদাহরণ নেব বুঝতে।
মান লেন, আমরা বাইনারি সার্চ টেকনিক ব্যবহার করছি। এই টেকনিকেই, আমরা চেক করি এলিমেন্টটি মাঝপথে আছে কিনা। যদি মাঝপথে থাকে, তবে অ্যালগরিদম টার্মিনেট হয়, অন্যথায় আমরা একচুই লেফট বা রাইট সাবঅ্যারে নিই আসল অ্যারে থেকে বারবার। তাই প্রতিটি ধাপে অ্যারের সাইজ n/2 করে কমে। মনে করুন বাইনারি সার্চ অ্যালগরিদম এক্সিকিউট হতে T(n) টাইম নেয়। বেস কন্ডিশন O(1) টাইম নেয়। তাই রিকারেন্স ইকুয়েশন হবে নিচের মতো −
$$T(n)=\begin{cases}T(1) & \text{for } n \leq 1\\T(\frac{n}{2})+c & \text{for } n > 1\end{cases}$$
সমাধান − প্রতিটি ধাপে ফর্মুলা সাবস্টিটিউট করে রেজাল্ট পাব −
$$T(n)=T(\frac{n}{2})+c$$
T(N/2) সাবস্টিটিউট করে লিখলে,
$$T(n)=(T(\frac{n}{4})+c)+c$$
$$T(n)=T(\frac{n}{4})+2c$$
$$T(n)=T(\frac{n}{8})+3c$$
$$T(n)=T(\frac{n}{2^{k}})+kc$$
এখন যদি $$(\frac{n}{2^{k}})$$ ১-এ পৌঁছায়, তবে বোঝা যায় 2k হলো n। তাই k-এর মান log2n
T(n)-র কমপ্লেক্সিটি = Θ(log n)
সহরূপ, যদি আমরা মার্জ সর্টের মতো অন্য উদাহরণ নিই, তবে সেটা লিস্টকে দুটি পার্টে ভাগ করে। এটি ভাগ করা চলবে যতক্ষণ না লিস্ট সাইজ ১ হয়। তারপর সেগুলো সোর্টেড অর্ডারে মার্জ করা হয়। মার্জিং অ্যালগরিদম O(n) টাইম নেয়। তাই যদি মার্জ সর্ট অ্যালগরিদম T(n) টাইম নেয়, তবে দুটি হাফে ভাগ করে প্রতিটির জন্য একই টাস্ক করলে সেগুলো T(n/2) টাইম নেবে এবং এভাবে চলবে। তাই রিকারেন্স রিলেশন হবে নিচের মতো −
$$T(n)=\begin{cases}T(1) & \text{for } n = 1\\2T(\frac{n}{2})+cn & \text{for } n > 1\end{cases}$$
সমাধান − প্রতিটি ধাপে ফর্মুলা সাবস্টিটিউট করে রেজাল্ট পাব −
$$T(n)=2T(\frac{n}{2})+cn$$
T(N/2) সাবস্টিটিউট করে লিখলে,
$$T(n)=2(2T(\frac{n}{4})+\frac{cn}{2}) +cn$$
$$T(n)=4T(\frac{n}{4}) +2cn$$
$$T(n)=8T(\frac{n}{8}) +3cn$$
$$T(n)=2^{k}T(\frac{n}{2^{k}}) +kcn$$
এখন যদি $$(\frac{n}{2^{k}})$$ ১-এ পৌঁছায়, তবে বোঝা যায় 2k হলো n। তাই k-এর মান log2n। এবং T(n) হবে −
𝑇(𝑛) = 𝑛𝑇(1) + 𝑐𝑛 log2𝑛
কমপ্লেক্সিটি হলো Θ(n log n)
