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

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

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

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

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

एक मानक ऐरे-आधारित मर्ज सॉर्ट कितनी अतिरिक्त मेमोरी का उपयोग करता है?

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

एमॉर्टाइज़्ड विश्लेषण (amortised analysis) क्या मापता है?

1. Aयादृच्छिक इनपुट पर अपेक्षित लागत
2. Bसबसे अच्छे इनपुट पर एल्गोरिदम की लागत
3. Cऑपरेशनों के वर्स्ट-केस अनुक्रम पर प्रति ऑपरेशन औसत लागत
4. Dपूरे अनुक्रम में कहीं भी अकेले सबसे महँगे ऑपरेशन की लागत

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

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

किसी समस्या में इष्टतम उप-संरचना (optimal substructure) होने का क्या अर्थ है?

1. Aएक इष्टतम समाधान उसकी उप-समस्याओं के इष्टतम समाधानों से बनाया जा सकता है
2. Bसमस्या का ठीक एक इष्टतम समाधान है, जो हर उप-समस्या में साझा होता है
3. Cहर उप-समस्या का आकार समान है
4. Dसमस्या को स्थिर समय में हल किया जा सकता है

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

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

क्लास NP की कौन-सी परिभाषा सही है?

1. Aसमस्याएँ जो बहुपदी नहीं हैं
2. Bसमस्याएँ जिन्हें कोई एल्गोरिदम हल नहीं कर सकता
3. Cनिर्णय समस्याएँ जिनके "हाँ" उत्तर किसी प्रमाणपत्र (certificate) के साथ बहुपदी समय में सत्यापित हो सकते हैं
4. Dसमस्याएँ जो बहुपदी समय में हल नहीं हो सकतीं