रिकरेंस रिलेशन के लिए प्रैक्टिस सेट

रिकरेंस रिलेशन (Recurrence Relations) वे समीकरण होते हैं जो बहुआयामी सरणी (Multidimensional Array) को पुनरावर्ती रूप से परिभाषित करते हैं।

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

प्रश्न 1:

रिकरेंस रिलेशन हल करें: T(n) = 12T(n/2) + 9n² + 2
यहाँ, a = 12, b = 2, और f(n) = 9n² + 2
यह f(n) = O(n^c) के रूप में है, जहाँ c = 2

यह मास्टर थ्योरम (Master's Theorem) की शर्त के अंतर्गत आता है।

log_b(a) = log₂(12) = 3.58
मास्टर थ्योरम के केस 1 का उपयोग करते हुए, T(n) = θ(n³·⁵⁸)

प्रश्न 2:

रिकरेंस रिलेशन हल करें: T(n) = 5T(n/2 + 23) + 5n² + 7n - 5/3

सरलीकरण पर, बड़े मानों के लिए n, n/2 >> 23, इसलिए 23 को नज़रअंदाज किया जा सकता है।

T(n) = 5T(n/2) + 5n² + 7n - 5/3
आगे, 5n² + 7n - 5/3 ≃ O(n²) लिया जा सकता है। इसलिए, T(n) = 5T(n/2) + O(n²)

यह मास्टर थ्योरम के केस 2 के अंतर्गत आता है।

अतः, T(n) = O(n²)

निम्नलिखित की जांच करें कि क्या ये मास्टर थ्योरम के किसी केस के अंतर्गत आते हैं:

T(n) = 2T(n/3) + 5ⁿ

नहीं, मास्टर थ्योरम लागू करने के लिए फंक्शन बहुपद (Polynomial) होना चाहिए।

T(n) = 2T(n/5) + tan(n)

नहीं, त्रिकोणमितीय फंक्शन (Trigonometric Function) मास्टर थ्योरम के अंतर्गत नहीं आते।

T(n) = 5T(n+1) + log(n)

नहीं, लॉगरिदमिक फंक्शन (Logarithmic Function) मास्टर थ्योरम के अंतर्गत नहीं आते।

T(n) = T(n-7) + eⁿ

नहीं, एक्सपोनेंशियल फंक्शन (Exponential Function) मास्टर थ्योरम के अंतर्गत नहीं आते।

T(n) = 9n(n/2+1) + 4n² - 17

हाँ, जैसा कि ऊपर हल किया गया है।