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

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

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

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

1. A9 सेकंड
2. B3 सेकंड
3. C6 सेकंड
4. D12 सेकंड

एडजेसेंसी लिस्ट (adjacency list) के रूप में संग्रहीत ग्राफ़ पर डेप्थ-फ़र्स्ट सर्च (DFS) की टाइम कॉम्प्लेक्सिटी क्या है?

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

क्विकसॉर्ट की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या है?

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

आधार k में d अंकों वाले n पूर्णांकों पर LSD रेडिक्स सॉर्ट का रनिंग टाइम क्या है?

1. AO(dn log k)
2. BO(n²)
3. CO(d(n + k))
4. DO(n log n)

एक सरल रिकर्सिव फ़ैक्टोरियल फ़ंक्शन fact(n) = n × fact(n − 1) कितना स्टैक स्पेस उपयोग करता है?

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

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

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

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

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