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

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

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

कौन-सा सॉर्टिंग एल्गोरिदम गलत क्रम में मौजूद आसन्न तत्वों को बार-बार आपस में बदलता है?

1. Aहीप सॉर्ट (Heap sort)
2. Bबबल सॉर्ट (Bubble sort)
3. Cक्विकसॉर्ट (Quicksort)
4. Dमर्ज सॉर्ट (Merge sort)

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

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

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

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

एक फ़ंक्शन n इटरेशन का एक लूप चलाता है और फिर, अलग से, n इटरेशन का एक और लूप। इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

मर्ज सॉर्ट के लिए डायनेमिक प्रोग्रामिंग कोई वास्तविक गति-वृद्धि क्यों नहीं देती?

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

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

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

V शीर्षों और E किनारों वाले ग्राफ़ पर बाइनरी हीप के साथ डाइकस्ट्रा के एल्गोरिदम का रनिंग टाइम क्या है?

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