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

n बड़ा होने पर इनमें से कौन सबसे धीमा बढ़ता है?

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

कौन-सा सॉर्टिंग एल्गोरिदम एक पिवट चुनकर ऐरे को छोटे और बड़े तत्वों में विभाजित करता है?

1. Aक्विकसॉर्ट (Quicksort)
2. Bबबल सॉर्ट
3. Cइंसर्शन सॉर्ट
4. Dमर्ज सॉर्ट

किसी एल्गोरिदम का वर्स्ट-केस रनिंग टाइम क्या बताता है?

1. Aधीमे कंप्यूटर पर लगने वाला समय
2. Bn आकार के सभी इनपुट पर लगने वाला अधिकतम समय
3. Cआकार n के किसी यादृच्छिक इनपुट पर लगने वाला अपेक्षित समय
4. Dसबसे छोटे इनपुट पर लगने वाला समय

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

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

मानक तीन लूप से दो n × n मैट्रिक्स गुणा करने की टाइम कॉम्प्लेक्सिटी क्या है?

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

प्रिम का एल्गोरिदम मिनिमम स्पैनिंग ट्री कैसे बनाता है?

1. Aयह एक प्रारंभिक शीर्ष से एक ट्री बढ़ाता है, और ट्री से बाहर जाने वाला सबसे सस्ता किनारा जोड़ता है
2. Bयह सबसे महँगा किनारा तब तक हटाता है जब तक कोई चक्र न बचे
3. Cयह ब्रेड्थ-फ़र्स्ट सर्च चलाकर BFS ट्री रखता है
4. Dयह सभी किनारों को भार के अनुसार सॉर्ट करता है और हर किनारे को तब तक जोड़ता है जब तक वह फ़ॉरेस्ट में चक्र (cycle) न बनाए

ट्रैवलिंग सेल्समैन समस्या का वर्गीकरण कैसे होता है?

1. Aयह अनिर्णेय है
2. Bनिर्णय रूप P में है पर ऑप्टिमाइज़ेशन रूप NP-complete है
3. Cयह P में है क्योंकि डाइकस्ट्रा का एल्गोरिदम हर शहर को एक बार देखकर इसे हल करता है
4. Dनिर्णय रूप NP-complete है और ऑप्टिमाइज़ेशन रूप NP-hard

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

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