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

स्पेस कॉम्प्लेक्सिटी (space complexity) क्या मापती है?

1. Aप्रोग्राम फ़ाइल के कंपाइल हो जाने के बाद उसका डिस्क स्पेस
2. Bकंप्यूटर का भौतिक आकार
3. Cइनपुट बढ़ने के साथ एल्गोरिदम को आवश्यक मेमोरी की मात्रा
4. Dकोड की पंक्तियों की संख्या

n तत्वों वाले अनसॉर्टेड ऐरे में लीनियर सर्च (linear search) की टाइम कॉम्प्लेक्सिटी (वर्स्ट केस) क्या है?

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

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

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

1,000,000 तत्वों के सॉर्टेड ऐरे पर बाइनरी सर्च को वर्स्ट केस में लगभग कितनी तुलनाएँ चाहिए?

1. Aलगभग 20
2. Bलगभग 1,000
3. Cलगभग 500,000
4. Dलगभग 100

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

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

एक फ़ंक्शन n इटरेशन का एक लूप चलाता है और फिर, अलग से, n इटरेशन का एक और लूप। इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

little-o नोटेशन के बारे में कौन-सा कथन सही है?

1. A2n = o(n), क्योंकि 2n धीरे बढ़ता है
2. Bn² = o(n)
3. Cn = o(n²), पर n, o(n) नहीं है
4. Dn = o(n), क्योंकि हर फलन स्वयं का little-o है

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

1. Aसमस्याएँ जिन्हें हर कंप्यूटर पर घातांकी समय चाहिए
2. Bसमस्याएँ जो समानांतर रूप से हल हो सकती हैं
3. Cनिर्णय समस्याएँ जो एक नियतात्मक (deterministic) एल्गोरिदम द्वारा बहुपदी समय में हल हो सकती हैं
4. Dसमस्याएँ जिनके समाधान जाँचे तो जा सकते हैं पर बहुपदी समय में कभी खोजे नहीं जा सकते