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

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

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

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

1. Aबेस्ट-केस और वर्स्ट-केस रनिंग टाइम के बीच का मध्य मान
2. Bn आकार के इनपुट के किसी दिए गए वितरण पर अपेक्षित समय
3. Cऔसत लंबाई वाले इनपुट का समय
4. Dसबसे आम कंप्यूटर पर समय

n संख्याओं के अनसॉर्टेड ऐरे में सबसे बड़ा मान खोजने की टाइम कॉम्प्लेक्सिटी क्या है?

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

V शीर्षों और E किनारों वाले ग्राफ़ पर बेलमैन–फ़ोर्ड एल्गोरिदम की टाइम कॉम्प्लेक्सिटी क्या है?

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

गैर-ऋणात्मक एज वेट वाले ग्राफ़ में एक स्रोत से सबसे छोटे पथ कौन-सा एल्गोरिदम खोजता है?

1. ADijkstra का एल्गोरिदम
2. BKruskal का एल्गोरिदम
3. Cडेप्थ-फ़र्स्ट सर्च (DFS)
4. Dहर स्थिति में Bellman–Ford आवश्यक है

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

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

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

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

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

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