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

एक O(n) एल्गोरिदम n = 10 लाख के लिए 3 सेकंड लेता है। n = 20 लाख के लिए लगभग कितना समय लगेगा?

1. A12 सेकंड
2. B9 सेकंड
3. C3 सेकंड
4. D6 सेकंड

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

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

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

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

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

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

एक सरल रिकर्सिव फ़ैक्टोरियल फ़ंक्शन fact(n) = n × fact(n − 1) कितना स्टैक स्पेस उपयोग करता है?

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

for i = 1 to n: (j = 1; while j < n: j = j × 2) — इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

हॉल्टिंग समस्या (halting problem) क्या दर्शाती है?

1. Aहर प्रोग्राम अंततः रुक जाता है
2. Bलूप से बचना चाहिए
3. Cकोई भी एल्गोरिदम हर प्रोग्राम और इनपुट के लिए यह तय नहीं कर सकता कि वह रुकेगा या नहीं
4. Dकुछ प्रोग्राम तेज़ कंप्यूटरों पर तेज़ चलते हैं, इसलिए रुकना हार्डवेयर पर निर्भर करता है

मास्टर प्रमेय का उपयोग करके T(n) = 8T(n/2) + O(n²) का हल क्या है?

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