उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट

डिवाइड-एंड-कॉन्कर एल्गोरिदम के तीन चरण कौन-से हैं?

1. Aसॉर्ट, सर्च, रिटर्न
2. Bअनुमान, जाँच, दोहराव
3. Cविभाजन (divide), विजय (conquer), संयोजन (combine)
4. Dपढ़ना, गणना, लिखना

सॉर्टेड ऐरे पर बाइनरी सर्च (binary search) की टाइम कॉम्प्लेक्सिटी क्या है?

1. AO(n log n)
2. BO(log n)
3. CO(n)
4. DO(1)

स्पेस कॉम्प्लेक्सिटी (space complexity) क्या मापती है?

1. Aप्रोग्राम फ़ाइल के कंपाइल हो जाने के बाद उसका डिस्क स्पेस
2. Bकंप्यूटर का भौतिक आकार
3. Cकोड की पंक्तियों की संख्या
4. Dइनपुट बढ़ने के साथ एल्गोरिदम को आवश्यक मेमोरी की मात्रा

एक सरल रिकर्सिव फ़ैक्टोरियल फ़ंक्शन fact(n) = n × fact(n − 1) कितना स्टैक स्पेस उपयोग करता है?

1. AO(1)
2. BO(log n)
3. CO(n²)
4. DO(n)

रिकरेंस T(n) = T(n/2) + O(1) का हल क्या है?

1. AO(log n)
2. BO(n log n)
3. CO(1)
4. DO(n)

for i = 1 to n: (j = 1; while j < n: j = j × 2) — इसकी टाइम कॉम्प्लेक्सिटी क्या है?

1. AO(n log n)
2. BO(n)
3. CO(n²)
4. DO(log n)

केवल अंतिम दो मान रखने वाले लूप से n-वीं फ़िबोनाची संख्या की गणना की समय और स्पेस लागत क्या है?

1. AO(n) समय और O(1) स्पेस
2. BO(2ⁿ) समय और O(1) स्पेस
3. CO(n) समय और O(n) स्पेस
4. DO(log n) समय और O(n) स्पेस

P और NP के बारे में कौन-सा कथन सही है?

1. ANP का अर्थ है "not polynomial"
2. BNP समस्याओं को जल्दी सत्यापित नहीं किया जा सकता
3. Cयह सिद्ध हो चुका है कि P ≠ NP
4. DP की हर समस्या NP में भी है