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

एक लूप i = 1 से शुरू होता है और हर इटरेशन में i को दोगुना करता है जब तक i > n न हो जाए। यह कितने इटरेशन चलता है?

1. Aलगभग n / 2
2. Bलगभग n
3. Cलगभग log₂ n
4. Dलगभग n²

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

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

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

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

m और n लंबाई की स्ट्रिंग्स के लॉन्गेस्ट कॉमन सबसीक्वेंस के लिए मानक डायनेमिक प्रोग्रामिंग एल्गोरिदम की टाइम कॉम्प्लेक्सिटी क्या है?

1. AO(m + n)
2. BO(mn)
3. CO(mn log n)
4. DO(2^m+n)

for i = 1 to n: (j = 1; while j < n: j = j × 2) — इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

सरल रिकर्सिव फ़िबोनाची (fib(n) = fib(n−1) + fib(n−2)) की टाइम कॉम्प्लेक्सिटी क्या है?

1. Aलघुगणकीय (Logarithmic)
2. Bघातांकी (Exponential)
3. Cरैखिक (Linear)
4. Dस्थिर (Constant)

करात्सुबा गुणन T(n) = 3T(n/2) + O(n) को संतुष्ट करता है। इसका हल क्या है?

1. AΘ(n³)
2. BΘ(n log n)
3. CΘ(n^{log₂ 3}), लगभग n^1.585
4. DΘ(n²)

क्लास P की कौन-सी परिभाषा सही है?

1. Aनिर्णय समस्याएँ जो एक नियतात्मक (deterministic) एल्गोरिदम द्वारा बहुपदी समय में हल हो सकती हैं
2. Bसमस्याएँ जिनके समाधान जाँचे तो जा सकते हैं पर बहुपदी समय में कभी खोजे नहीं जा सकते
3. Cसमस्याएँ जिन्हें हर कंप्यूटर पर घातांकी समय चाहिए
4. Dसमस्याएँ जो समानांतर रूप से हल हो सकती हैं