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

एल्गोरिदम क्या है?

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

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

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

f(n) = Θ(g(n)) का क्या अर्थ है?

1. Af, g से सख़्ती से तेज़ बढ़ता है
2. Bf, g से सख़्ती से धीमा बढ़ता है
3. Cहर n के लिए f हमेशा g से छोटा है, इसलिए g उसे ऊपर से सीमित करता है पर नीचे से कभी नहीं
4. Df, g की ही दर से बढ़ता है, और ऊपर व नीचे दोनों ओर g के स्थिर गुणजों से सीमित है

एक सॉर्टेड ऐरे में आप दोनों सिरों से एक-एक पॉइंटर को भीतर की ओर खिसकाते हुए ऐसे दो तत्व खोजते हैं जिनका योग लक्ष्य के बराबर हो। टाइम कॉम्प्लेक्सिटी क्या है?

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

सरल रिकर्सिव फ़िबोनाची (fib(n) = fib(n−1) + fib(n−2)) की टाइम कॉम्प्लेक्सिटी क्या है?

1. Aघातांकी (Exponential)
2. Bलघुगणकीय (Logarithmic)
3. Cरैखिक (Linear)
4. Dस्थिर (Constant)

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

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

यदि कोई किसी एक NP-complete समस्या के लिए बहुपदी-समय एल्गोरिदम खोज ले, तो क्या निष्कर्ष निकलेगा?

1. ANP की हर समस्या बहुपदी समय में हल हो सकेगी, इसलिए P = NP
2. Bकेवल वही एक समस्या P में चली जाएगी
3. Cहॉल्टिंग समस्या निर्णेय हो जाएगी
4. Dसभी घातांकी-समय एल्गोरिदम तुरंत रैखिक समय में चलने लगेंगे

बाइनरी काउंटर को बढ़ाने (increment) की एमॉर्टाइज़्ड लागत क्या है, यह देखते हुए कि एक वृद्धि कई बिट पलट सकती है?

1. Aप्रति वृद्धि O(log n)
2. Bप्रति वृद्धि O(1)
3. Cप्रति वृद्धि O(n log n)
4. Dप्रति वृद्धि O(n)