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

एडजेसेंसी लिस्ट (adjacency list) के रूप में संग्रहीत ग्राफ़ पर डेप्थ-फ़र्स्ट सर्च (DFS) की टाइम कॉम्प्लेक्सिटी क्या है?

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

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

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

किसी समस्या को सामान्यतः सुसाध्य (tractable) कब कहा जाता है?

1. Aजब उसे केवल हर संभावना आज़माकर हल किया जा सके
2. Bजब उसका कोई समाधान न हो
3. Cजब उसे बहुपदी समय में हल किया जा सके
4. Dजब उसे स्थिर समय में हल किया जा सके

रिकरेंस T(n) = T(n − 1) + O(1) का हल क्या है?

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

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

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

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

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

सॉर्टेड ऐरे में किसी भी तुलना-आधारित खोज को वर्स्ट केस में Ω(log n) तुलनाएँ क्यों चाहिए?

1. Aहर तत्व की कम से कम एक बार तुलना होनी चाहिए
2. Bहर तुलना में लघुगणकीय समय लगता है
3. Cn संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
4. Dबाइनरी सर्च ही एकमात्र संभव एल्गोरिदम है, और उसे log₂ n तुलनाएँ चाहिए

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

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