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

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

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

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

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

ब्रूट-फ़ोर्स एल्गोरिदम क्या है?

1. Aवह जो यादृच्छिक रूप से उत्तर का अनुमान लगाता है
2. Bवह जो सभी संभावित उम्मीदवार समाधान आज़माता है
3. Cवह जो हमेशा रिकर्शन का उपयोग करता है
4. Dवह जो कई प्रोसेसरों पर चलता है

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

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

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

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

आप n तत्वों का ऐरे एक बार सॉर्ट करते हैं और फिर बाइनरी सर्च से k सदस्यता प्रश्नों के उत्तर देते हैं। कुल लागत क्या है?

1. AO(n + k)
2. BO(nk)
3. CO(n log n + k log n)
4. DO(k n log n)

नैपसैक के किस रूप के लिए ग्रीडी नियम "वस्तुओं को प्रति भार मूल्य के क्रम में लें" हमेशा इष्टतम उत्तर देता है?

1. Aकोई भी रूप नहीं
2. B0/1 नैपसैक, जिसमें वस्तुएँ हमेशा पूरी ली जानी चाहिए
3. Cदोनों रूप
4. Dफ़्रैक्शनल नैपसैक, जिसमें वस्तुएँ बाँटी जा सकती हैं

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

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