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

सॉर्टेड ऐरे पर बाइनरी सर्च (binary search) की टाइम कॉम्प्लेक्सिटी क्या है?

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

O(2ⁿ) वृद्धि को क्या कहते हैं?

1. Aलघुगणकीय (logarithmic)
2. Bरैखिक (linear)
3. Cबहुपदी (polynomial)
4. Dघातांकी (exponential)

किसी एल्गोरिदम का वर्स्ट-केस रनिंग टाइम क्या बताता है?

1. Aआकार n के किसी यादृच्छिक इनपुट पर लगने वाला अपेक्षित समय
2. Bn आकार के सभी इनपुट पर लगने वाला अधिकतम समय
3. Cसबसे छोटे इनपुट पर लगने वाला समय
4. Dधीमे कंप्यूटर पर लगने वाला समय

कौन-सा सॉर्टिंग एल्गोरिदम स्थिर (stable) है?

1. Aसेलेक्शन सॉर्ट (सामान्य संस्करण)
2. Bहीप सॉर्ट
3. Cक्विकसॉर्ट (सामान्य इन-प्लेस संस्करण)
4. Dमर्ज सॉर्ट

मर्ज सॉर्ट के लिए डायनेमिक प्रोग्रामिंग कोई वास्तविक गति-वृद्धि क्यों नहीं देती?

1. Aडायनेमिक प्रोग्रामिंग केवल ग्राफ़ समस्याओं पर काम करती है, ऐरे पर नहीं
2. Bमर्ज सॉर्ट पहले से ही O(n) है
3. Cइसकी उप-समस्याएँ अतिव्यापी नहीं हैं, इसलिए दोबारा उपयोग करने को कुछ नहीं है
4. Dमर्ज सॉर्ट की कोई रिकर्सिव संरचना नहीं है

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

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

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

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

यह सिद्ध करने के लिए कि कोई निर्णय समस्या X NP-complete है, कौन-सी दो बातें दिखानी होंगी?

1. AX, NP में है, और कोई ज्ञात NP-complete समस्या बहुपदी समय में X में रिड्यूस होती है
2. BX, P की किसी समस्या में रिड्यूस होती है, और X, NP में है
3. CX का कोई बहुपदी एल्गोरिदम नहीं है, और X निर्णेय है
4. DX, P में है, और X, SAT में रिड्यूस होती है