यहां हम देखेंगे कि पुनरावृत्ति संबंधों को हल करने के लिए प्रतिस्थापन विधि का उपयोग कैसे करें। इसे बेहतर तरीके से समझने के लिए हम दो उदाहरण लेंगे।
मान लीजिए हम बाइनरी सर्च तकनीक का उपयोग कर रहे हैं। इस तकनीक में हम जांचते हैं कि तत्व अंत में मौजूद है या नहीं। यदि वह बीच में मौजूद है, तो एल्गोरिथ्म समाप्त हो जाता है, अन्यथा हम बार-बार वास्तविक सरणी से बाएँ और दाएँ उप-सरणी लेते हैं। तो प्रत्येक चरण में सरणी का आकार n / 2 से कम हो जाता है। मान लीजिए कि द्विआधारी खोज एल्गोरिथ्म को निष्पादित करने में T(n) समय लगता है। आधार स्थिति में O(1) समय लगता है। तो पुनरावर्ती समीकरण नीचे जैसा होगा -
$$T(n)=\begin{cases}T(1) &for\:n \leq 1\\2T(\frac{n}{2})+c &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 तक पहुंच जाता है, तो यह इंगित करता है कि 2 k एन है। तो k का मान log2 . है
T(n) =ϴ(log n)
. की जटिलताइसी तरह, यदि हम मर्ज सॉर्ट जैसा कोई अन्य उदाहरण चुनते हैं, तो उस स्थिति में हम सूची को दो भागों में विभाजित करते हैं। यह विभाजन तब तक हो रहा है जब तक सूची का आकार केवल 1 नहीं है। उसके बाद हम उन्हें क्रमबद्ध क्रम में मिलाते हैं। मर्जिंग एल्गोरिथम में O(n) समय लगता है। इसलिए यदि मर्ज सॉर्ट एल्गोरिथम T(n) समय ले रहा है, तो इसे दो हिस्सों में विभाजित करके, और उनमें से प्रत्येक के लिए एक ही कार्य करें, वे T(n/2) लेंगे और इसी तरह। तो पुनरावर्तन संबंध नीचे जैसा होगा -
$$T(n)=\begin{cases}T(1) &for\:n =1\\2T(\frac{n}{2})+cn &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 तक पहुंच जाता है, तो यह इंगित करता है कि 2 k एन है। तो k का मान log2 . है . और T(n) होगा -
𝑇(𝑛) =𝑛𝑇(1) + 𝑐𝑛 लॉग<उप>2
जटिलता है θ(n log n)