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

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

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

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

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

f(n) = Θ(g(n)) का क्या अर्थ है?

1. Af, g से सख़्ती से धीमा बढ़ता है
2. Bf, g से सख़्ती से तेज़ बढ़ता है
3. Cहर n के लिए f हमेशा g से छोटा है, इसलिए g उसे ऊपर से सीमित करता है पर नीचे से कभी नहीं
4. Df, g की ही दर से बढ़ता है, और ऊपर व नीचे दोनों ओर g के स्थिर गुणजों से सीमित है

वर्स्ट केस में तुलना-आधारित (comparison-based) सॉर्टिंग की निचली सीमा क्या है?

1. AΩ(n²)
2. BΩ(n)
3. CΩ(n log n)
4. DΩ(log n)

गैर-ऋणात्मक एज वेट वाले ग्राफ़ में एक स्रोत से सबसे छोटे पथ कौन-सा एल्गोरिदम खोजता है?

1. Aहर स्थिति में Bellman–Ford आवश्यक है
2. Bडेप्थ-फ़र्स्ट सर्च (DFS)
3. CDijkstra का एल्गोरिदम
4. DKruskal का एल्गोरिदम

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

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

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

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

हेल्ड–कार्प डायनेमिक प्रोग्रामिंग एल्गोरिदम ट्रैवलिंग सेल्समैन समस्या को ठीक-ठीक हल करता है। n शहरों के लिए इसका रनिंग टाइम क्या है?

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