यहां हम देखेंगे कि पुनरावृत्ति संबंधों को हल करने के लिए प्रतिस्थापन विधि का उपयोग कैसे करें। हम इसे बेहतर तरीके से समझने के लिए दो उदाहरण लेंगे।
मान लें हम बाइनरी सर्च तकनीक का उपयोग कर रहे हैं। इस तकनीक में, हम जांचते हैं कि तत्व मध्य में मौजूद है या नहीं। यदि वह मध्य में मौजूद है, तो एल्गोरिदम समाप्त हो जाता है, अन्यथा हम वास्तविक ऐरे से फिर से बाएं या दाएं सबऐरे लेते हैं। इसलिए प्रत्येक चरण में ऐरे का आकार 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}})$$ 1 तक पहुंचता है, तो यह इंगित करता है कि 2k n है। इसलिए k का मान log2n है
T(n) की जटिलता = Θ(log n)
इसी तरह, यदि हम मर्ज सॉर्ट जैसे एक और उदाहरण चुनते हैं, तो उस मामले में हम लिस्ट को दो भागों में विभाजित करते हैं। यह विभाजन तब तक होता है जब तक लिस्ट का आकार केवल 1 नहीं हो जाता। उसके बाद हम उन्हें सॉर्टेड ऑर्डर में मर्ज करते हैं। मर्जिंग एल्गोरिदम 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}})$$ 1 तक पहुंचता है, तो यह इंगित करता है कि 2k n है। इसलिए k का मान log2n है। और T(n) होगा -
𝑇(𝑛) = 𝑛𝑇(1) + 𝑐𝑛 log2𝑛
जटिलता है Θ(n log n)
