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

इनमें से कौन-सा रनिंग टाइम बहुपदी (polynomial) है?

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

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

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

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

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

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

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

n तत्वों के ऐरे के लिए मर्ज सॉर्ट के रिकर्शन में कितने स्तर होते हैं?

1. Aलगभग n
2. Bलगभग n / 2
3. Cलगभग log₂ n
4. Dलगभग √n

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

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

स्ट्रासेन का एल्गोरिदम आधे आकार के ब्लॉकों के 8 के बजाय 7 रिकर्सिव गुणनों से मैट्रिक्स गुणा करता है। इसका रनिंग टाइम क्या है?

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

बॉटम-अप विधि से n अनसॉर्टेड तत्वों से बाइनरी हीप बनाने की टाइम कॉम्प्लेक्सिटी क्या है?

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