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

किसी एल्गोरिदम का रनिंग टाइम O(n) है। इस वृद्धि को क्या कहते हैं?

1. Aद्विघाती (quadratic)
2. Bस्थिर (constant)
3. Cरैखिक (linear)
4. Dलघुगणकीय (logarithmic)

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

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

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

1. AΩ (Big Omega)
2. Bo (little o)
3. CO (Big O)
4. DΘ (Big Theta)

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

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

क्विकसॉर्ट हमेशा पहले तत्व को पिवट के रूप में उपयोग करता है। किस इनपुट पर यह अपना वर्स्ट-केस व्यवहार दिखाता है?

1. Aऐसा ऐरे जिसके सभी तत्व भिन्न हैं
2. Bलंबाई 2 का ऐरे
3. Cएक ऐरे जो पहले से सॉर्टेड है
4. Dयादृच्छिक क्रम वाला ऐरे

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

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

log(n!) के लिए कौन-सी सीमा सही है?

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

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

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