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

डिवाइड-एंड-कॉन्कर एल्गोरिदम के तीन चरण कौन-से हैं?

1. Aविभाजन (divide), विजय (conquer), संयोजन (combine)
2. Bसॉर्ट, सर्च, रिटर्न
3. Cपढ़ना, गणना, लिखना
4. Dअनुमान, जाँच, दोहराव

ऐरे में इंडेक्स द्वारा किसी तत्व तक पहुँचने में कितना समय लगता है?

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

कौन-सा सॉर्टिंग एल्गोरिदम गलत क्रम में मौजूद आसन्न तत्वों को बार-बार आपस में बदलता है?

1. Aबबल सॉर्ट (Bubble sort)
2. Bक्विकसॉर्ट (Quicksort)
3. Cहीप सॉर्ट (Heap sort)
4. Dमर्ज सॉर्ट (Merge sort)

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

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

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

1. AO(n)
2. BO(log n)
3. CO(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³)

बाइनरी काउंटर को बढ़ाने (increment) की एमॉर्टाइज़्ड लागत क्या है, यह देखते हुए कि एक वृद्धि कई बिट पलट सकती है?

1. Aप्रति वृद्धि O(n)
2. Bप्रति वृद्धि O(log n)
3. Cप्रति वृद्धि O(1)
4. Dप्रति वृद्धि O(n log n)

सॉर्टेड ऐरे में किसी भी तुलना-आधारित खोज को वर्स्ट केस में Ω(log n) तुलनाएँ क्यों चाहिए?

1. Aबाइनरी सर्च ही एकमात्र संभव एल्गोरिदम है, और उसे log₂ n तुलनाएँ चाहिए
2. Bहर तुलना में लघुगणकीय समय लगता है
3. Cn संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
4. Dहर तत्व की कम से कम एक बार तुलना होनी चाहिए