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

यदि कोई ऑपरेशन O(1) समय में चलता है, तो इसका क्या अर्थ है?

1. Aउसका रनिंग टाइम इनपुट आकार के साथ नहीं बढ़ता
2. Bउसमें हमेशा ठीक एक सेकंड लगता है
3. Cवह रनिंग टाइम के प्रति सेकंड ठीक एक तत्व संसाधित करता है
4. Dउसे केवल एक बार चलाया जा सकता है

log₂ 1024 क्या है?

1. A512
2. B10
3. C32
4. D12

रिकर्शन (recursion) क्या है?

1. Aएक फ़ंक्शन जो छोटे इनपुट पर स्वयं को कॉल करता है
2. Bएक लूप जो कभी समाप्त नहीं होता
3. Cएक प्रकार की डेटा संरचना
4. Dएक सॉर्टिंग विधि

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

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

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

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

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

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

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

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

P और NP के बारे में कौन-सा कथन सही है?

1. ANP का अर्थ है "not polynomial"
2. Bयह सिद्ध हो चुका है कि P ≠ NP
3. CNP समस्याओं को जल्दी सत्यापित नहीं किया जा सकता
4. DP की हर समस्या NP में भी है