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

दो नेस्टेड लूप वाले एल्गोरिदम की, जिनमें से प्रत्येक n बार चलता है, सामान्यतः कौन-सी कॉम्प्लेक्सिटी होती है?

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

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

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

किसी रिकर्सिव फ़ंक्शन का बेस केस क्या है?

1. Aवह कॉल जो सबसे अधिक मेमोरी लेती है
2. Bफ़ंक्शन की पहली पंक्ति
3. Cवह स्थिति जिसका उत्तर बिना कोई और रिकर्सिव कॉल किए सीधे दिया जाता है
4. Dसबसे बड़े इनपुट वाली स्थिति, जिसे किसी भी रिकर्सिव कॉल से पहले संभाला जाता है

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

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

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

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

1, 3 और 4 के सिक्कों और 6 की राशि के साथ, ग्रीडी "पहले सबसे बड़ा सिक्का" विधि इष्टतम की तुलना में कितने सिक्के उपयोग करती है?

1. Aग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 3 है
2. Bग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 2 है
3. Cग्रीडी 2 सिक्के उपयोग करती है; इष्टतम 2 है
4. Dग्रीडी 4 सिक्के उपयोग करती है; इष्टतम 3 है

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

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

करात्सुबा गुणन T(n) = 3T(n/2) + O(n) को संतुष्ट करता है। इसका हल क्या है?

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