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

एक O(n) एल्गोरिदम n = 10 लाख के लिए 3 सेकंड लेता है। n = 20 लाख के लिए लगभग कितना समय लगेगा?

1. A9 सेकंड
2. B6 सेकंड
3. C12 सेकंड
4. D3 सेकंड

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

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

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

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

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

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

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

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

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

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

यह दिखाने के लिए कि कोई नई समस्या X NP-hard है, आपको क्या करना होगा?

1. AX को बहुपदी समय में किसी ज्ञात NP-hard समस्या में रिड्यूस करना
2. Bदिखाना कि छोटे इनपुट के लिए X का कोई बहुपदी एल्गोरिदम नहीं है
3. Cदिखाना कि X बहुपदी समय में सत्यापित हो सकती है
4. Dकिसी ज्ञात NP-hard समस्या को बहुपदी समय में X में रिड्यूस करना

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

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