অ্যালগরিদম অ্যানালিসিস করার সময় আমরা কিছু রিকারেন্স রিলেশন পাই। এই রিকারেন্স রিলেশনগুলো মূলত একই ফাংশন এক্সপ্রেশনে ব্যবহার করে। অধিকাংশ কেসে রিকার্সিভ অ্যালগরিদম অ্যানালিসিস এবং ডিভাইড অ্যান্ড কনকার অ্যালগরিদমে রিকারেন্স রিলেশন পাওয়া যায়।
এখানে আমরা কিছু উদাহরণ দিয়ে একটি রিকারেন্স ইকুয়েশন দেখব। মান লেন, আমরা বাইনারি সার্চ টেকনিক ব্যবহার করছি। এই টেকনিকেই, আমরা চেক করি এলিমেন্টটি মাঝপথে আছে কিনা। যদি মাঝপথে থাকে, তবে অ্যালগরিদম টার্মিনেট হয়, অন্যথায় আমরা একচুই লেফট বা রাইট সাবঅ্যারে নিই আসল অ্যারে থেকে বারবার। তাই প্রতিটি ধাপে অ্যারের সাইজ 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}$$
সহরূপ, যদি আমরা মার্জ সর্টের মতো অন্য উদাহরণ নিই, তবে সেটা লিস্টকে দুটি পার্টে ভাগ করে। এটি ভাগ করা চলবে যতক্ষণ না লিস্ট সাইজ শুধু ১ হয়। তারপর সেগুলো সোর্টেড অর্ডারে মার্জ করা হয়। মার্জিং অ্যালগরিদম 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}$$
এই ইকুয়েশনগুলো আমরা বিভিন্ন মেথড দিয়ে সমাধান করতে পারি, যেমন সাবস্টিটিউশন, রিকারেন্স ট্রি মেথড, এবং কিছু স্পেশাল কин্ডের রিকারেন্স রিলেশন মাস্টার মেথড দিয়ে সমাধান করা যায়।
