पुनरावृत्ति संबंधों के लिए अभ्यास सेट

पुनरावृत्ति संबंध ऐसे समीकरण हैं जो एक बहुआयामी सरणी को पुनरावर्ती रूप से परिभाषित करते हैं।

यहां हम पुनरावृत्ति संबंधों पर आधारित ऐसे प्रश्नों को हल करेंगे।

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.