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

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

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

यदि कोई ऑपरेशन O(1) समय में चलता है, तो इसका क्या अर्थ है?

1. Aउसका रनिंग टाइम इनपुट आकार के साथ नहीं बढ़ता
2. Bउसे केवल एक बार चलाया जा सकता है
3. Cवह रनिंग टाइम के प्रति सेकंड ठीक एक तत्व संसाधित करता है
4. Dउसमें हमेशा ठीक एक सेकंड लगता है

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

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

एक ग्रीडी एल्गोरिदम (greedy algorithm):

1. Aहर संभव समाधान आज़माता है
2. Bकेवल रिकर्शन का उपयोग करता है
3. Cहमेशा इष्टतम समाधान देता है
4. Dहर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है

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

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

भर जाने पर अपनी क्षमता दोगुनी करने वाले डायनेमिक ऐरे में तत्व जोड़ने (append) की एमॉर्टाइज़्ड (amortised) टाइम कॉम्प्लेक्सिटी क्या है?

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

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

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

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

1. AΘ(n)
2. BΘ(n log n)
3. CΘ(n log² n)
4. DΘ(n²)