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

बड़े n के लिए कौन-सा कॉम्प्लेक्सिटी क्लास सबसे तेज़ी से बढ़ता है?

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

सिलेक्शन सॉर्ट (selection sort) कैसे काम करता है?

1. Aयह बार-बार ग़लत क्रम वाले पड़ोसी तत्वों को स्वैप करता है
2. Bयह ऐरे को आधे भागों में बाँटकर उन्हें मर्ज करता है
3. Cयह हर तत्व को शिफ़्ट करके बढ़ते सॉर्टेड भाग में डालता है
4. Dयह बार-बार अनसॉर्टेड भाग का न्यूनतम खोजकर उसे आगे की ओर स्वैप करता है

किसी एल्गोरिदम का रनिंग टाइम O(n) है। इस वृद्धि को क्या कहते हैं?

1. Aलघुगणकीय (logarithmic)
2. Bद्विघाती (quadratic)
3. Cस्थिर (constant)
4. Dरैखिक (linear)

डायनेमिक प्रोग्रामिंग (dynamic programming) तब उपयोगी है जब किसी समस्या में हों:

1. Aकोई उप-समस्या बिल्कुल न हो, ताकि उसे एक ही चरण में हल किया जा सके
2. Bओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
3. Cकेवल यादृच्छिक इनपुट
4. Dकेवल एक लूप

1,000,000 तत्वों के सॉर्टेड ऐरे पर बाइनरी सर्च को वर्स्ट केस में लगभग कितनी तुलनाएँ चाहिए?

1. Aलगभग 100
2. Bलगभग 500,000
3. Cलगभग 20
4. Dलगभग 1,000

क्विकसॉर्ट की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या है?

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

क्या 2²ⁿ, O(2ⁿ) में है?

1. Aहाँ, क्योंकि Big O में घातांक के स्थिर गुणक हमेशा अनदेखे किए जाते हैं
2. Bनहीं, क्योंकि 2²ⁿ = 4ⁿ और 4ⁿ / 2ⁿ = 2ⁿ असीमित रूप से बढ़ता है
3. Cनहीं, क्योंकि 2²ⁿ, 2ⁿ से धीमा बढ़ता है
4. Dहाँ, क्योंकि दोनों घातांकी हैं

क्लास P की कौन-सी परिभाषा सही है?

1. Aनिर्णय समस्याएँ जो एक नियतात्मक (deterministic) एल्गोरिदम द्वारा बहुपदी समय में हल हो सकती हैं
2. Bसमस्याएँ जिनके समाधान जाँचे तो जा सकते हैं पर बहुपदी समय में कभी खोजे नहीं जा सकते
3. Cसमस्याएँ जो समानांतर रूप से हल हो सकती हैं
4. Dसमस्याएँ जिन्हें हर कंप्यूटर पर घातांकी समय चाहिए