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

कौन-सा नोटेशन वृद्धि की निचली सीमा (lower bound) को दर्शाता है?

1. Ao (little o)
2. BΘ (Big Theta)
3. CΩ (Big Omega)
4. DO (Big O)

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

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

कौन-सा नोटेशन वृद्धि की ऊपरी सीमा (upper bound) को दर्शाता है?

1. ABig Omega
2. BBig O
3. CLittle omega
4. DBig Theta

आधार k में d अंकों वाले n पूर्णांकों पर LSD रेडिक्स सॉर्ट का रनिंग टाइम क्या है?

1. AO(dn log k)
2. BO(d(n + k))
3. CO(n²)
4. DO(n log n)

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

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

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

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

for i = 1 to n: for (j = i; j ≤ n; j = j + i) O(1) कार्य करें — इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

बेलमैन–फ़ोर्ड एल्गोरिदम स्रोत से पहुँच योग्य ऋणात्मक-भार चक्र का पता कैसे लगाता है?

1. Aयह जाँचता है कि क्या किसी किनारे का भार ऋणात्मक है
2. Bयह डेप्थ-फ़र्स्ट सर्च से चक्र गिनता है
3. CV − 1 दौरों के बाद यह जाँचता है कि क्या कोई किनारा अब भी रिलैक्स हो सकता है
4. Dयह डाइकस्ट्रा का एल्गोरिदम दो बार चलाकर दोनों दूरी परिणामों की तुलना करता है