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

n तत्वों वाले अनसॉर्टेड ऐरे में लीनियर सर्च (linear search) की टाइम कॉम्प्लेक्सिटी (वर्स्ट केस) क्या है?

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

एडजेसेंसी लिस्ट (adjacency list) के रूप में संग्रहीत ग्राफ़ पर डेप्थ-फ़र्स्ट सर्च (DFS) की टाइम कॉम्प्लेक्सिटी क्या है?

1. AO(V + E)
2. BO(V²)
3. CO(V × E)
4. DO(E log V)

3n² + 5n + 2 का Big O क्या है?

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

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

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

क्या यह कहना सही है कि एक O(n²) एल्गोरिदम O(n³) भी है?

1. Aहाँ, क्योंकि Big O एक ऊपरी सीमा है और n², n³ से तेज़ नहीं बढ़ता
2. Bनहीं, क्योंकि बड़े n के लिए n³, n² से छोटा है
3. Cनहीं, क्योंकि Big O को हमेशा फ़ंक्शन की सटीक वृद्धि दर बतानी चाहिए
4. Dहाँ, पर केवल तब जब n 100 से छोटा हो

कई लाइब्रेरी सॉर्टिंग रूटीन बहुत छोटे सबऐरे के लिए इंसर्शन सॉर्ट पर क्यों चली जाती हैं?

1. Aइंसर्शन सॉर्ट का ओवरहेड कम है और यह छोटे या लगभग सॉर्टेड इनपुट पर तेज़ है
2. Bइंसर्शन सॉर्ट वर्स्ट केस में O(n log n) है
3. Cरिकर्सिव एल्गोरिदम 10 से कम तत्वों वाले ऐरे नहीं सँभाल सकते
4. Dबड़े इनपुट पर इंसर्शन सॉर्ट किसी भी अन्य सॉर्टिंग एल्गोरिदम से कम मेमोरी उपयोग करता है

करात्सुबा गुणन T(n) = 3T(n/2) + O(n) को संतुष्ट करता है। इसका हल क्या है?

1. AΘ(n²)
2. BΘ(n log n)
3. CΘ(n^{log₂ 3}), लगभग n^1.585
4. DΘ(n³)

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

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