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

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

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

स्पेस कॉम्प्लेक्सिटी (space complexity) क्या मापती है?

1. Aकोड की पंक्तियों की संख्या
2. Bइनपुट बढ़ने के साथ एल्गोरिदम को आवश्यक मेमोरी की मात्रा
3. Cकंप्यूटर का भौतिक आकार
4. Dप्रोग्राम फ़ाइल के कंपाइल हो जाने के बाद उसका डिस्क स्पेस

f(n) = Θ(g(n)) का क्या अर्थ है?

1. Aहर n के लिए f हमेशा g से छोटा है, इसलिए g उसे ऊपर से सीमित करता है पर नीचे से कभी नहीं
2. Bf, g की ही दर से बढ़ता है, और ऊपर व नीचे दोनों ओर g के स्थिर गुणजों से सीमित है
3. Cf, g से सख़्ती से धीमा बढ़ता है
4. Df, g से सख़्ती से तेज़ बढ़ता है

एमॉर्टाइज़्ड विश्लेषण (amortised analysis) क्या मापता है?

1. Aऑपरेशनों के वर्स्ट-केस अनुक्रम पर प्रति ऑपरेशन औसत लागत
2. Bपूरे अनुक्रम में कहीं भी अकेले सबसे महँगे ऑपरेशन की लागत
3. Cयादृच्छिक इनपुट पर अपेक्षित लागत
4. Dसबसे अच्छे इनपुट पर एल्गोरिदम की लागत

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

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

for i = 1 to n: for j = 1 to i: O(1) कार्य करें — इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

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

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

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

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