পুনরাবৃত্তি সম্পর্ক এমন সমীকরণ যা পুনরাবৃত্তিমূলকভাবে একটি বহুমাত্রিক অ্যারেকে সংজ্ঞায়িত করে।
এখানে আমরা পুনরাবৃত্তি সম্পর্কের উপর ভিত্তি করে প্রশ্নগুলি সমাধান করব।
Solve the recurrence reation:T(n) = 12T(n/2) + 9n2 + 2. T(n) = 12T(n/2) + 9n2 + 2. Here, a = 12 and b = 2 and f(n) = 9(n)2 + 2 It is of the form f(n) = O(n^c), where c = 2
এটি মাস্টার্স থিওরেম অবস্থায়,
So, logb(a) = log2(12) = 3.58 Using case 1 of the masters theorm, T(n) = θ(n3.58).
Solve the recurrence reation: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. Further, we can take 5n2 + 7n - 5 ≃0(n2). So, T(n) = 5T(n/2) + O(n2)
এটি মাস্টার্স থিওরেমের কেস 2 এর অধীনে পড়ে,
So, 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 Yes, as solved above.
