एल्गोरिदम के विश्लेषण के दौरान, हम कुछ पुनरावृत्ति संबंध पाते हैं। ये पुनरावृत्ति संबंध मूल रूप से अभिव्यक्ति में उसी फंक्शन का उपयोग कर रहे हैं। रिकर्सिव एल्गोरिदम विश्लेषण, और डिवाइड एंड कंकर एल्गोरिदम के अधिकांश मामलों में हमें पुनरावृत्ति संबंध मिलते हैं।
यहां हम कुछ उदाहरणों की मदद से पुनरावृत्ति समीकरण का एक उदाहरण देखेंगे। मान लें हम बाइनरी सर्च तकनीक का उपयोग कर रहे हैं। इस तकनीक में, हम जांचते हैं कि तत्व अंत में मौजूद है या नहीं। यदि वह मध्य में मौजूद है, तो एल्गोरिदम समाप्त हो जाता है, अन्यथा हम वास्तविक ऐरे से बार-बार बाएं और दाएं सबऐरे लेते हैं। इसलिए प्रत्येक चरण में ऐरे का आकार 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}$$
इसी तरह, यदि हम मर्ज सॉर्ट जैसे एक और उदाहरण चुनते हैं, तो उस मामले में हम लिस्ट को दो भागों में विभाजित करते हैं। यह विभाजन तब तक होता है जब तक लिस्ट का आकार केवल 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}$$
हम इन समीकरणों को विभिन्न विधियों का उपयोग करके हल कर सकते हैं, जैसे प्रतिस्थापन, पुनरावृत्ति ट्री विधि, और कुछ विशेष प्रकार के पुनरावृत्ति संबंधों को मास्टर मेथड का उपयोग करके हल किया जा सकता है।
