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

दो नेस्टेड लूप वाले एल्गोरिदम की, जिनमें से प्रत्येक n बार चलता है, सामान्यतः कौन-सी कॉम्प्लेक्सिटी होती है?

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

किसी समस्या को सामान्यतः सुसाध्य (tractable) कब कहा जाता है?

1. Aजब उसे केवल हर संभावना आज़माकर हल किया जा सके
2. Bजब उसका कोई समाधान न हो
3. Cजब उसे बहुपदी समय में हल किया जा सके
4. Dजब उसे स्थिर समय में हल किया जा सके

O(2ⁿ) वृद्धि को क्या कहते हैं?

1. Aरैखिक (linear)
2. Bलघुगणकीय (logarithmic)
3. Cबहुपदी (polynomial)
4. Dघातांकी (exponential)

एक्टिविटी सिलेक्शन समस्या में कौन-सा ग्रीडी नियम हमेशा अधिकतम संख्या में न-अतिव्यापी गतिविधियाँ देता है?

1. Aसबसे जल्दी शुरू होने वाली गतिविधि चुनें
2. Bपहले सबसे छोटी गतिविधि चुनें
3. Cसबसे जल्दी समाप्त होने वाली गतिविधि चुनें, फिर संगत गतिविधियों के साथ दोहराएँ
4. Dपहले सबसे कम अतिव्यापन वाली गतिविधि चुनें, फिर संगत गतिविधियों के साथ दोहराएँ

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

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

एक ग्रीडी एल्गोरिदम (greedy algorithm):

1. Aहर संभव समाधान आज़माता है
2. Bहमेशा इष्टतम समाधान देता है
3. Cकेवल रिकर्शन का उपयोग करता है
4. Dहर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है

सॉर्टेड ऐरे में किसी भी तुलना-आधारित खोज को वर्स्ट केस में Ω(log n) तुलनाएँ क्यों चाहिए?

1. An संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
2. Bहर तुलना में लघुगणकीय समय लगता है
3. Cहर तत्व की कम से कम एक बार तुलना होनी चाहिए
4. Dबाइनरी सर्च ही एकमात्र संभव एल्गोरिदम है, और उसे log₂ n तुलनाएँ चाहिए

कुक–लेविन प्रमेय ने क्या स्थापित किया?

1. Aबूलियन संतुष्टि समस्या (SAT) NP-complete है
2. Bहर NP समस्या घातांकी समय में हल हो सकती है
3. CP, NP के बराबर नहीं है
4. Dहॉल्टिंग समस्या अनिर्णेय (undecidable) है