পুনরাবৃত্তি সম্পর্ক (Recurrence relations) এমন সমীকরণ যা একটি বহুমাত্রিক অ্যারেকে পুনরাবৃত্তিমূলকভাবে সংজ্ঞায়িত করে।
এখানে আমরা পুনরাবৃত্তি সম্পর্কের উপর ভিত্তি করে কিছু প্রশ্ন সমাধান করব।
পুনরাবৃত্তি সম্পর্ক সমাধান করুন: T(n) = 12T(n/2) + 9n2 + 2. T(n) = 12T(n/2) + 9n2 + 2. এখানে, a = 12 এবং b = 2 এবং f(n) = 9(n)2 + 2 এটি f(n) = O(n^c) ফর্মের, যেখানে c = 2
এটি মাস্টার থিওরেমের শর্তে পড়ে,
তবে, logb(a) = log2(12) = 3.58 মাস্টার থিওরেমের কেস ১ ব্যবহার করে, T(n) = θ(n3.58)
পুনরাবৃত্তি সম্পর্ক সমাধান করুন: T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3. T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3
সরলীকরণে, বড় মানগুলোর ক্ষেত্রে, n, n/2 >> 23, তাই 23 কে উপেক্ষা করা যায়।
T(n) = 5T(n/2) + 5n2 + 7n - 5/3. আরও, আমরা 5n2 + 7n - 5 ≃0(n2) নিতে পারি। সুতরাং, T(n) = 5T(n/2) + O(n2)
এটি মাস্টার থিওরেমের কেস ২-এ পড়ে,
তবে, T(n) = O(n2)
নিচের موارد যেকোনো মাস্টার থিওরেমের কেসের অধীনে পড়ে কিনা যাচাই করুন।
T(n) = 2T(n/3) + 5n
না, মাস্টার থিওরেম প্রযোজ্য হওয়ার জন্য ফাংশনটি একটি পলিনোমিয়াল ফাংশন হতে হবে।
T(n) = 2T(n/5) + tan(n)
না, ত্রিকোণমিতিক ফাংশন মাস্টার থিওরেমের অধীনে আসে না।
T(n) = 5T(n+1) + log(n)
না, লগারিদমিক ফাংশন মাস্টার থিওরেমের অধীনে আসে না।
T(n) = T(n-7) + en
না, এক্সপোনেনশিয়াল ফাংশন মাস্টার থিওরেমের অধীনে আসে না।
T(n) = 9n(n/2+1 ) + 4(n2) - 17 হ্যাঁ, উপরে সমাধান করা হয়েছে।
