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

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

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

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

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

मेमोइज़ेशन (memoisation) क्या है?

1. Aकोड की हर पंक्ति के आगे टिप्पणियाँ लिखना
2. Bफ़ंक्शन लौटने के बाद मेमोरी मुक्त करना
3. Cफ़ंक्शन कॉल के परिणाम संग्रहीत करना ताकि दोहराई गई कॉल का उत्तर मेमोरी से मिले
4. Dरिकर्शन को अपने आप समतुल्य लूप में बदलना ताकि कॉल स्टैक की आवश्यकता न रहे

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

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

पहुँच योग्य बेस केस के बिना रिकर्सिव फ़ंक्शन के बारे में कौन-सा कथन सही है?

1. Aयह O(1) समय में चलता है
2. Bयह अपने आप 0 लौटाता है
3. Cयह तब तक स्वयं को कॉल करता रहता है जब तक कॉल स्टैक ओवरफ़्लो न हो जाए
4. Dकंपाइलर हमेशा इसे ऐसे लूप में बदल देता है जो सुरक्षित रूप से समाप्त होता है

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

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

कौन-सा एल्गोरिदम बार-बार ऐसा सबसे सस्ता एज जोड़कर, जो चक्र न बनाए, मिनिमम स्पैनिंग ट्री खोजता है?

1. ADijkstra का एल्गोरिदम
2. BKruskal का एल्गोरिदम
3. Cएक नोड से शुरू होने वाला Prim का एल्गोरिदम
4. DFloyd–Warshall

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

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