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

कौन-सा नोटेशन वृद्धि की ऊपरी सीमा (upper bound) को दर्शाता है?

1. ABig O
2. BBig Omega
3. CLittle omega
4. DBig Theta

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

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

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

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

बिना वेट वाले ग्राफ़ पर ब्रेड्थ-फ़र्स्ट सर्च (BFS) क्या खोजता है?

1. Aसभी ग्राफ़ों में एक टोपोलॉजिकल क्रम
2. Bऋणात्मक एज वेट वाले ग्राफ़ में सबसे छोटे पथ
3. Cप्रारंभिक नोड से एज की संख्या के अनुसार सबसे छोटे पथ
4. Dमिनिमम स्पैनिंग ट्री

किसी समस्या में इष्टतम उप-संरचना (optimal substructure) होने का क्या अर्थ है?

1. Aसमस्या को स्थिर समय में हल किया जा सकता है
2. Bसमस्या का ठीक एक इष्टतम समाधान है, जो हर उप-समस्या में साझा होता है
3. Cहर उप-समस्या का आकार समान है
4. Dएक इष्टतम समाधान उसकी उप-समस्याओं के इष्टतम समाधानों से बनाया जा सकता है

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

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

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

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

क्या 2²ⁿ, O(2ⁿ) में है?

1. Aहाँ, क्योंकि दोनों घातांकी हैं
2. Bनहीं, क्योंकि 2²ⁿ = 4ⁿ और 4ⁿ / 2ⁿ = 2ⁿ असीमित रूप से बढ़ता है
3. Cहाँ, क्योंकि Big O में घातांक के स्थिर गुणक हमेशा अनदेखे किए जाते हैं
4. Dनहीं, क्योंकि 2²ⁿ, 2ⁿ से धीमा बढ़ता है