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

कौन-सा नोटेशन वृद्धि की ऊपरी सीमा (upper bound) को दर्शाता है?

1. ABig O
2. BBig Theta
3. CLittle omega
4. DBig Omega

इंसर्शन सॉर्ट (insertion sort) की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या है?

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

कौन-सा सॉर्टिंग एल्गोरिदम एक पिवट चुनकर ऐरे को छोटे और बड़े तत्वों में विभाजित करता है?

1. Aमर्ज सॉर्ट
2. Bक्विकसॉर्ट (Quicksort)
3. Cबबल सॉर्ट
4. Dइंसर्शन सॉर्ट

Big O में, जैसे O(log n) में, लघुगणक का आधार सामान्यतः क्यों छोड़ दिया जाता है?

1. Aभिन्न आधारों वाले लघुगणक केवल एक स्थिर गुणक से भिन्न होते हैं
2. Bआधार केवल छोटे n के लिए मायने रखता है
3. Cलघुगणक हमेशा पूर्णांकों में पूर्णांकित किए जाते हैं
4. Dकंप्यूटर विज्ञान में सभी लघुगणकों का आधार 10 होता है, इसलिए वह निहित है

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

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

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

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

करात्सुबा गुणन T(n) = 3T(n/2) + O(n) को संतुष्ट करता है। इसका हल क्या है?

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n^{log₂ 3}), लगभग n^1.585
4. DΘ(n log n)

little-o नोटेशन के बारे में कौन-सा कथन सही है?

1. An² = o(n)
2. Bn = o(n²), पर n, o(n) नहीं है
3. C2n = o(n), क्योंकि 2n धीरे बढ़ता है
4. Dn = o(n), क्योंकि हर फलन स्वयं का little-o है