Time Complexity for Coding Interviews | Big O Notation Explained | Data Structures & Algorithms

हाय एवरीवन और आज के इस लेक्चर के अंदर हम सीखने वाले हैं टाइम कॉम्प्लेक्टेड करते हैं c+ प के अंदर करते हैं पाइथन के अंदर करते हैं जावास्क्रिप्ट के अंदर करते हैं बिल्कुल भी लैंग्वेज स्पेसिफिक हमारा लेक्चर नहीं होने वाला इसके अंदर सारी की सारी जो डिस्कशन है वो हम कांसेप्चुअली करेंगे जो हर लैंग्वेज के ऊपर अप्लाई करते हैं अब टाइम कंपलेक्सिटी डीएसए के अंदर एक ऐसा कांसेप्ट है जो हमें बहुत ज्यादा कंफ्यूज करता है क्यों क्योंकि इसके अंदर हम बहुत सारी थोरेट्स प्रॉब्लम्स को सॉल्व करने जाते हैं तो हमें समझ में नहीं आता कि

कैसे वो सारी थ्योरी हमारी प्रॉब्लम सॉल्विंग के अंदर फिट इन करती है तो वही चीज एक्चुअली आज के सेशन के अंदर हम सीखने वाले हैं तो फर्स्ट पार्ट के अंदर पहले हम टाइम कंपलेक्सिटी का एक तरीके से रिवीजन करेंगे तो अगर आपको ऑलरेडी टाइम कॉम्प्लेक्शन को देख सकते हैं अगर आपने आज तक टाइम कॉम्प्लेक्शन को हम देख सकते हैं ताकि हम जान सके कि टाइम कॉम्प्लेक्शन वर्क वर्क कैसे करती है जब भी हम एल्गोरिथम्स की बात करते हैं एंड फिर सेकंड सेक्शन के अंदर हम जान रहे होंगे कि कैसे जो हमारी टीसी की नॉलेज है

वो हमें हेल्प करती है जब हम प्रॉब्लम्स को सॉल्व करने जाते हैं क्योंकि कई बार जब हमें कोई क्वेश्चन दिया जाता है सॉल्व करने के लिए तो उसके अंदर कंस्ट्रेंट्स को देखकर हम एक्चुअली गेस कर सकते हैं कि इस क्वेश्चन की एक्सपेक्टेड टाइम कंपलेक्सिटी या इस क्वेश्चन का एक्सपेक्टेड सॉल्यूशन क्या होने वाला है तो सबसे पहले स्टार्ट करते हैं अपने रिवीजन के साथ हम बात करेंगे कि टाइम कॉम्प्लेक्शन होती क्या है अब टाइम कप्ले के अंदर टाइम वर्ड आता है तो कई बार स्टूडेंट्स यहां पे गेस करते हैं कि क्या पता जो हम कोड लिखते

हैं जो हम एल्गोरिदम लिखते हैं क्या पता यह उसका रन टाइम है टाइम कॉम्प्लेक्शन बहुत गलत गेस है टाइम कॉम्प्लेक्शन राइट इट हियर टाइम कॉम्प्लेक्शन इज नॉट इक्वल टू द एक्चुअल टाइम टेकन बाय दी एल्गोरिथम यानी हो सकता है कि आपने कोई सिंपल सा कोड है वो कोई फॉर लूप भी हो सकता है वो कुछ भी हो सकता है वही सिंपल सा कोड अगर आप लीड कोड के ऊपर सबमिट करेंगे और वही कोड जाकर आप कोड फोर्सेस के ऊपर सबमिट करेंगे या किसी और प्लेटफॉर्म के ऊपर सबमिट करेंगे तो सेम एल्गोरिदम के लिए सेम कोड

के लिए आपको डिफरेंट एग्जीक्यूशन टाइम मिल सकता है इसके अलावा हो सकता है कि सेम कोड आप किसी मैक मशीन के अंदर रन करें और सेम कोड किसी विंडोज मशीन के अंदर रन करें और सेम कोड को किसी बात नहीं करते यानी हम यह बात नहीं करते कि एक सेकंड लगेगा या 100 मिली सेकंड्स लगेंगे या 400 मिली सेकंड्स लगेंगे या 500 मिली सेकंड्स लगेंगे हम एक रिलेशन की बात करते हैं हम एक बिहेवियर की बात करते हैं और एक रिलेशन बिहेवियर क्या होता है वो अभी हम धीरे-धीरे जान रहे होंगे पर सबसे पहले तो

एक क्लेरिटी होनी चाहिए कि हो सकता है आपके और आपके दोस्त ने सेम कोड लिखा हो पर डिफरेंट मशीनस पे रन करें या डिफरेंट प्लेटफॉर्म्स के ऊपर जाके रन करें तो आपका कोड डिफरेंट टाइम में एग्जीक्यूट बिल्कुल हो सकता है क्योंकि जो एक्चुअल रन टाइम होता है वो बहुत सारे फैक्टर्स के ऊपर डिपेंड करता है वो इस पर भी डिपेंड करता है कि आपके सिस्टम के क्या कॉन्फिन है कौन सा ऑपरेटिंग सिस्टम आप यूज़ कर रहे हैं वो इस पर भी डिपेंड करता है कि लीड कोड ने अलग सर्वर कॉन्फिडेंस रख रखे हैं कोड फोर्सेस

के अलग कॉन्फिन हैं एंड किसी और कोडिंग प्लेटफॉर्म्स के डिफरेंट कॉन्फिन है तो हमें डिफरेंट टाइम टेकन मिल सकता है तो टाइम कॉम्प्लेक्शन है क्या टाइम कॉम्प्लेक्शन है बेसिकली टाइम कॉप्लेक्स टी हमें बताता है कि कोई भी कोड है उसके अंदर जो भी इनपुट आ रहा है वो इनपुट कैसे उस कोड के नंबर ऑफ ऑपरेशंस को अफेक्ट करता है मतलब अगर हमने कोई भी सिंपल सा एल्गोरिदम लिखा हुआ है फॉर एग्जांपल दिस इज़ माय सिंपल एल्गोरिदम ये एक फॉर लूप भी हो सकता है इसके अंदर कोई ना कोई इनपुट तो आ रहा होगा कोई इनपुट

हमारा एक एरे भी हो सकता है ये इनपुट हो सकता है कोई मैप हो ये इनपुट हो सकता है कोई स्ट्रिंग हो या ये कुछ और इनपुट भी हो सकता है जो भी इनपुट है उसका साइज वेरी कर सकता है यानी अगर हम एक सिंपल एरे का एग्जांपल लें तो एरे तो एक एक सिंगल एलिमेंट का भी हो सकता है एरे पांच एलिमेंट्स का भी हो सकता है एरे 10 मिलियन एलिमेंट का भी हो सकता है तो ये जो एरे का साइज है या जो इनपुट का साइज है वो कैसे इस कोड के नंबर ऑफ

ऑपरेशंस को बढ़ाएगा डिक्रीज करेगा कैसे नंबर ऑफ ऑपरेशंस चेंज होंगे बेस्ड अपऑन दिस इनपुट साइज सो दिस इज द बिहेवियर दिस इज द फंक्शन जो हमारे एल्गोरिदम से निकल के आएगा या कई सारी बुक्स के अंदर एक्सप्लेनेशन के लिए इसे ऐसे भी बताया जाता है कि कैसे इनपुट साइज के बढ़ने पर हमारा एल्गोरिदम कितना टाइम लेगी वो कैसे बढ़ रहा है किस प्रोपोर्शन में बढ़ रहा है उसे हम अपनी टाइम कॉम्प्लेक्शन सा एक एग्जांपल लेते हैं फॉर एग्जांपल मैंने लिखा एक फॉर लूप अपने किसी एरे के लिए फॉर लूप के अंदर लेट्स सपोज वी आर

स्टार्टिंग फ्रॉम द इंडेक्स रो इंडेक्स रो से हम अपने एरे के साइज n तक जा रहे हैं और हम हर बार i प्स प्स कर रहे हैं और हर बार हम क्या प्रिंट करवाने की कोशिश कर रहे हैं हम प्रिंट करवाने की कोशिश कर रहे हैं अपने एरे का आत एलिमेंट यह मैंने सिंपल सा एक फॉर लूप लिखा है अब क्या मैं कह सकती हूं कि जब मेरे एरे का जो इनपुट साइज है दैट इज इक्वल टू 0 तो उस टाइम पर मेरे कितने नंबर ऑफ ऑपरेशंस होंगे क्योंकि क्योंकि मेरा लूप रन ही नहीं करेगा

तो नंबर ऑफ ऑपरेशंस भी नहीं होंगे तो यहां पे 0 बा 0 का एक मुझे पॉइंट मिलेगा कि जब मेरा इनपुट साइज जीरो है तब मेरे नंबर ऑफ ऑपरेशंस भी जरो हो सकते हैं किसी एक पर्टिकुलर कोड के अंदर या जरो नहीं तो हो सकता है किसी केस में हमारे पास सिंपल एक ही ऑपरेशन परफॉर्म हो दो ही ऑपरेशंस परफॉर्म हो इस तरीके का कुछ मेरे पास पॉइंट निकल के आ सकता है अब अगर मैं अज्यू करूं कि मेरे एरे की जो लेंथ है दिस लेंथ n अगर ये 100 के बराबर है तो ओवरऑल मेरा

ये लूप कितनी बार रन करेगा मेरा लूप भी करीबन 100 बार रन करेगा तो क्या मैं अज्यू कर सकती हूं अराउंड 100 ऑपरेशंस को हम परफॉर्म कर रहे होंगे तो यहां पे जब मेरा इनपुट साइज लेट्स सपोज यहां पे 100 आता है तो यहां पे करीबन 100 ऑपरेशंस को हम परफॉर्म करेंगे तो मेरा नेक्स्ट जो पॉइंट आएगा वो मेरे ग्राफ में कुछ यहां पे दिखाई देगा कि जब इनपुट साइज 100 है तो ऑपरेशंस भी 100 के करीबन होने वाले हैं और अगर वहीं को कल को ये n इंक्रीज होकर हो गया 10000 के इक्वल तो

हो सकता है मेरा 10000 कुछ यहां पर लाई करता हो अब ये बिल्कुल स्केल वाला वाला ग्राफ नहीं है बहुत अजमन के साथ चीजें चल रही हैं तो यहीं पर करीबन मेरा 10000 वाला पॉइंट लाई करेगा और यह मीट कहां पर होंगे ग्राफ के अंदर ये कुछ यहां पर मीट हो रहे होंगे उसके बाद हो सकता है कल को मेरा n इंक्रीज होके इट बिकम 10 मिलियन 10 मिलियन वैसे तो इस ग्राफ में बहुत आगे होगा पर अजमन के लिए मैं उसे यहां लगा देती हूं तो यह भी जो इनका मीटिंग पॉइंट होगा कुछ यहां

पर होगा तो ये क्या है ये पॉइंट्स क्या है ये पॉइंट्स बिहेवियर को रिप्रेजेंट करते हैं और जब इन सारे पॉइंट्स को मिला के हम एक स्ट्रेट लाइन लेकर जाते हैं तो यह क्या होता है दिस बिहेवियर दिस फंक्शन इज एक्चुअली माय टाइम कॉम्प्लेक्टेड टाइम कॉम्प्लेक्टेड के नंबर ऑफ ऑपरेशंस किस प्रोपोर्शन में इंक्रीज हुए किस बिहेवियर के साथ इंक्रीज हुए और ये जो बिहेवियर है ये मेरा एक लीनियर बिहेवियर कहलाता है ये एक पर्टिकुलर टाइम कॉम्प्लेक्शन कॉम्प्लेक्शन रि रिजेंट करते हैं बिग ऑफ n के साथ तो कई बार आपने बिग ऑफ n की टाइम कॉम्प्लेक्शन

का अगर ग्राफ बनाया जाए तो इस तरीके की एक स्ट्रेट लाइन ऊपर की तरफ जाती हुई हमें दिखाई देती है और ये जो ग्राफ है मैथमेटिकली दिस इज अ ग्राफ ऑफ y = x यानी जैसे जैसे हमारे इनपुट का साइज बढ़ेगा वैसे-वैसे ही हमारे नंबर ऑफ ऑपरेशंस उसी प्रोपोर्शन में बढ़ रहे होंगे तो यहां से हमारा कांसेप्ट निकल के आता है टाइम कॉम्प्लेक्टेड के बढ़ने के साथ हमारे नंबर ऑफ ऑपरेशंस इंक्रीज होते हैं अब जब भी हम टाइम लिखना चाहते हैं यहां पे जैसे मैंने बिग ओ लिखा तो टाइम कॉम्प्लेन के अलग-अलग तरीके होते हैं

इन सारे तरीकों को हम नोटेशंस कहते हैं इफ आई राइट इट हियर हमारे पास डिफरेंट डिफरेंट नोटेशंस होती हैं हमने डिफरेंट डिफरेंट नोटेशंस पढ़ी होंगी थोरेट्स हमारे लिए ये इंपॉर्टेंट नहीं है प्रैक्टिकली सबसे ज्यादा जो इंपॉर्टेंट नोटेशन होती है दैट इज कॉल्ड बिग ओ बिकॉज इट्स लिटरली अ बिग ओ बिग ओ नोटेशन बताता है कि हमारा वर्स्ट केस क्या होगा मतलब हमारी वर्स्ट केस टाइम कॉप्लेक्स टी क्या होने वाली है अब यहां पे सबसे पहला सवाल दिमाग में आ सकता है कि नोटेशन क्या होती है नोटेशन इज बेसिकली अ सिंबल किसी चीज को दिखाने का

तरीका मैं कैसे दिखाऊं कि मेरे पास एक डॉलर है तो मैं क्या करूंगी डॉलर नोटेशन को यूज करूंगी मैं कैसे दिखाऊं कि मेरे पास एक रुपी है तो मैं क्या करूंगी रुपी नोटेशन को यूज करूंगी तो नोटेशन कुछ नहीं होता नोटेशन बस एक सिंबल होता है चीज को दिखाने का तरीका होता है और ऐसे ही टाइम डिफरेंट नोटेशंस है अब इसमें सबसे इंपॉर्टेंट नोटेशन हमारे पासस बिगो आ गई है और बिगो नोटेशन इज इंपॉर्टेंट क्यों क्योंकि हमारे लिए वर्स्ट के सिनेरियो यानी सबसे बड़ी वैल्यू ही सबसे इंपॉर्टेंट होती है इसको एक एग्जांपल के थ्रू समझते

हैं मैं एक तरफ आपको दूं ₹10 और दूसरी तरफ मैंने आपके लिए रख दिए ₹1 करोड़ तो कौन सी वैल्यू सबसे ज्यादा इंपॉर्टेंट हो जाएगी ओबवियसली जो वैल्यू साइज में बड़ी है वो सबसे ज्यादा इंपॉर्टेंट हो जाएगी हमारे लिए इस पॉइंट ऑफ डिस्कशन के लिए तो वैसे ही जब भी हम वर्स्ट केस टाइम कॉम्प्लेक्शन की बात करते हैं तो बिगो नोटेशन सबसे बड़ी वैल्यू हमें देता है और वो हमारे लिए सबसे ज्यादा इंपॉर्टेंट हो जाती है इसको एक और एग्जांपल के थ्रू समझ सकते हैं एक वेबसाइट है जिसके ऊपर 10 यूजर्स आते हैं और दूसरी

वेबसाइट है जिसके ऊपर 1 बिलियन यूजर्स आते हैं या 10 मिलियन यूजर्स आते हैं तो कौन सी वेबसाइट ज्यादा स्टेबल होगी ओबवियसली ये सेकंड वाली वेबसाइट ज्यादा स्टेबल होगी क्योंकि ये ज्यादा लोड ले सकती है इसे ज्यादा स्केलेबल बनाया गया है ज्यादा यूजर्स को यह कैटर कर सकती है तो मतलब इसकी एल्गोरिथम इसका सिस्टम काफी अच्छे से डिज़ाइन है तो हम क्या करते हैं हम हमेशा वर्स्ट केस के हिसाब से सोचते हैं हम यह सोचकर अपनी कोई भी वेबसाइट या कोई भी सिस्टम नहीं बनाते कि हमारे पास 10 यूज़र आ रहे होंगे 100 यूज़र आ

रहे होंगे हम हमेशा इस तरीके से अपने सिस्टम्स को बनाते हैं कि हमारे पास 10 मिलियन यूजर्स आएंगे हमारे पास 1 बिलियन यूजर्स आएंगे वो एक्चुअली स्ट्रांग सिस्टम्स होते हैं तो यहां पे टाइम कॉम्प्लेक्टेड मस को हम यूज़ करें व ठीक है बेस्ट केस सिनेरियो में तो वर्क कर जाएंगी एवरेज में भी वर्क कर जाएंगी पर क्या वो वर्स्ट केस सिनेरियो को विदस्टैंड कर पाएंगी तो उसके लिए हम अपना मेजर जो रखते हैं प्रैक्टिकल सारे केसेस के अंदर वो होता है हमारे बिग ओ का तो इसीलिए जब भी हम किसी भी इंटरव्यू के अंदर बैठते

हैं और हमसे टाइम कॉम्प्लेक्शन बिगो टाइम कॉम्प्लेक्टेड की टाइम कॉम्प्लेक्शन कैलकुलेट करनी होती है हम किसी कोडिंग टेस्ट के अंदर बैठे हैं तब भी हम बिगो को ही कैलकुलेट करते हैं बिकॉज़ प्रैक्टिकली दिस इज यूज्ड द मोस्ट तो हम इसी को लेकर मतलब बिगो को ही बेस बना के अपने आगे ये सारे डिस्कशंस कर रहे होंगे अब अभी हमने जाना कि हमारा जो इनपुट एंड ऑपरेशन के बीच का फंक्शन है जो रिलेशन है उसी को हम अपनी टाइम कॉम्प्लेक्शन कैन बी एनी मैथमेटिकल फंक्शन मैथ के अंदर फंक्शन कोई भी वैल्यू ले सकते हैं मैथ की

अगर बात करें तो मैथ के अंदर हम जनरली देखते थे fx2 लिख दिया ये क्या है एक फंक्शन है अगर मैंने लिख दिया fx5 n क + 2 टू पा n ये क्या है ये एक फंक्शन है तो मैथ का कोई भी फंक्शन टाइम कॉम्प्लेक्शन बन सकता है पर जनरली अगर हमारे पास बहुत सारे एक्सप्रेशंस आ जाते हैं तो हम इनमें से हमेशा सबसे बड़ा एक्सप्रेशन लेते हैं तो यही रीज़न है कि जब भी टाइम कॉम्प्लेक्शन को इग्नोर कर देते हैं और सबसे वर्स्ट वैल्यू को हम लेके आते हैं क्यों क्योंकि हमें हमेशा वर्स्ट के

सिनेरियो को ध्यान में रखना है तो उसमें फॉर एग्जांपल अगर मुझे एक टाइम कॉम्प्लेक्शन है बिग ऑफ n क या इसे 5n क + 2n स् + 52 इस तरीके की अगर मुझे टाइम कॉम्प्लेक्शन को हटाएंगे क्योंकि जब हम 1 बिलियन 10 मिलियन इतनी बड़ी वैल्यूज के बारे में सोच रहे हैं तो ये छोटे-छोटे कांस्टेंट्स हमारी ओवरऑल टाइम कॉम्प्लेक्शन पे कोई चेंज नहीं लाने वाले इसीलिए हम हमेशा कांस्टेंट्स को इग्नोर कर देते हैं दूसरी चीज हम क्या इग्नोर करेंगे हमारे पास जितनी भी डिफरेंट डिफरेंट वैल्यूज हैं हम उनमें से वर्स्ट वैल्यू निकालते हैं अब n

क प्रैक्टिकली हमेशा n स् से बड़ा होगा और n स् हमेशा इस वैल्यू से बड़ा होगा तो क्या मैं कह सकती हूं इस n स् को और इस चीज को हम कंप्लीट इग्नोर कर सकते हैं हमारी जो ओवरऑल टाइम कॉम्प्लेक्टेड इज गोइंग टू बी बिग ऑफ n क तो जब भी हमें टाइम कॉम्प्लेक्शन कांस्टेंट्स को इग्नोर करना है छोटी वैल्यूज को इग्नोर करना है और हमेशा बड़ी वैल्यू के ऊपर फोकस करना है क्योंकि वही हमारी ओवरऑल टाइम कॉम्प्लेक्शन है अच्छा यहां पर काफी सारे स्टूडेंट्स के दिमाग में एक डाउट आता है उनके दिमाग में डाउट

आता है कि जब भी हम टाइम े भी अपने कोड के लिए ऐसे फॉर्मूले लिखने होंगे तो इसका जवाब है बिल्कुल भी नहीं यानी अगर आपने डीएसए के 50 टू 70 क्वेश्चंस कर लिए और आपको ऑलरेडी टाइम कॉम्लेक्स टी की नॉलेज है तो एक ऐसा पॉइंट आएगा जिसके बाद आप लिटरली अपने कोड को पढ़ के अपनी टाइम कॉम्प्लेक्शन सा लूप है मुझे कोई कैलकुलेशन नहीं करनी पड़ रही कोई ऑपरेशंस नहीं करने पढ़ रहे देखने के लिए कि मेरा ये जो लूप है ये बिग ऑफ n का है क्योंकि n टाइम्स रन करेगा तो जब हम

एन नंबर ऑफ क्वेश्चन सॉल्व कर लेते हैं तो आपके लिए भी एक पॉइंट ऐसा आएगा जब आप लिटरली अपने कोड को देखकर बता पाएंगे कि इसकी रनिंग टाइम कॉम्प्लेक्शन खराब है कौन सी टाइम कॉम्प्लेक्शन है फॉर अ पर्टिकुलर क्वेश्चन तो शुरुआत में एक दो दिन हो सकता है कि टाइम कॉम्लेक्स को थोरेट्स को देख रहे हो इस तरीके की इक्वेशंस को सॉल्व कर रहे हो पर प्रैक्टिकली इंटरव्यूज के अंदर बैठकर कोई इतनी बड़ी-बड़ी इक्वेशंस को सॉल्व नहीं कर रहा होता जनरली हम एक अंदाजा लगा के अपनी टाइम बट वो फेज हमारा तब आएगा जब हम

इनफ नंबर ऑफ क्वेश्चंस को सॉल्व कर लेंगे अब अपने पुराने डिस्कशन पे आ जाते हैं हमने बात कर ली कि टाइम कंपलेक्सिटीज बेसिकली है फंक्शन अब मैथ के अंदर तो फंक्शन कुछ भी हो सकते हैं इसका मतलब टाइम कॉम्प्लेक्टेड नंबर ऑफ वैल्यूज हैं जो टाइम कॉम्प्लेक्टेड है जो हमें ज्यादा देखने को मिलती है टाइम कॉम्प्लेक्टेड को और डिटेल में समझने वाले हैं अब हमने बात की थी कि टाइम कॉम्प्लेक्शन अ फंक्शन तो फंक्शन की तो कोई भी वैल्यूज हो सकती हैं इनफाइनों सकती हैं जो एक मैथ वाले फंक्शन की हो सकती हैं वैसे ही टाइम

कॉम्प्लेक्शन की भी इनफाइनों सकती हैं डिपेंडिंग अपॉन कि हमने क्या एल्गोरिथम लिखा हुआ है बट प्रैक्टिकली जब हम डीएसए के सवाल सॉल्व करने जाते हैं तो कुछ पर्टिकुलर वैल्यूज ऐसी होती हैं जैसे बिग ऑफ व हो गया बिग ऑफ n हो गया बिग ऑफ l n हो गया जो हमें बार-बार बार-बार देखने को मिलती है तो अगर इन टाइम कॉम्प्लेक्शन की वैल्यूज को हम अच्छे से समझ जाते हैं तो हमारे लिए बाकी एल्गोरिथम्स की कॉम्प्लेक्शन वैल्यूज को कैलकुलेट करना बहुत आसान हो जाता है तो हम क्या करेंगे इन्हीं वैल्यूज को एक-एक करके डिटेल में समझेंगे

तो कॉमन कॉम्प्लेक्शन कॉम्प्लेक्शन टाइम कॉम्प्लेक्शन को हम इग्नोर करते हैं पर एक कांस्टेंट अकेला कांस्टेंट ऐसा जिसे हम इग्नोर नहीं करते दैट इज बिग ऑफ वन यानी ये वन वाला कांस्टेंट कांस्टेंट टाइम कॉम्प्लेक्शन ऑफ ऑपरेशंस एल्गोरिथम में उतने ही लगेंगे जैसे फॉर एग्जांपल आपने कोई फंक्शन बना दिया इस फंक्शन के अंदर हम कोई एरे है जिसको इनपुट ले रहे हैं और कोड के अंदर यानी फंक्शन के अंदर हम क्या कर रहे हैं फंक्शन के अंदर हम प्रिंट करवा रहे हैं हेलो वर्ल्ड इस तरीके से हमने हेलो वर्ल्ड प्रिंट करवा दिया अब यहां पर चाहे हमारे

एरे का साइज 10 हो चाहे हमारे एरे का साइज 10 मिलियन हो क्या हमारे नंबर ऑफ ऑपरेशंस बढ़ेंगे बिल्कुल नहीं बढ़ेंगे क्योंकि हर बार फंक्शन को क्या करना है एक ही ऑपरेशन परफॉर्म करना है व्हिच इज टू प्रिंट हेलो वर्ल्ड तो ये क्या हो गई ये कांस्टेंट टाइम कॉम्प्लेक्शन डिपेंड नहीं करते नंबर ऑफ ऑपरेशंस कांस्टेंट रहेंगे तो इसका ग्राफ कैसा दिखाई देता है कांस्टेंट टाइम कॉम्प्लेक्शन ग्राफ प्लॉट करने जाते हैं तो उसका ग्राफ एक स्ट्रेट लाइन होता है यानी इस तरीके का ग्राफ इज कांस्टेंट टाइम कॉम्प्लेक्शन ये थोड़ा सा वर्टिकली ऊपर भी हो सकता है

नीचे भी हो सकता है डिपेंडिंग अपॉन व्हाट आर द नंबर ऑफ कांस्टेंट ऑपरेशंस परट जनरली जब भी आपको स्ट्रेट लाइन दिखे दैट इज अ कांस्टेंट टाइम कॉम्प्लेक्शन टाइम हम किसी एरे की बात करें अगर मुझे एरे के अंदर पता है कि मुझे किसी पर्टिकुलर इंडेक्स पे जाके वैल्यू को एक्सेस करना है तो मुझे ऑलरेडी इंडेक्स पता है मुझे ऑलरेडी एरे का नाम पता है तो क्या मैं कह सकती हूं ये कांस्टेंट यानी बिग ऑफ वन का ऑपरेशन है क्योंकि सारी चीजें ऑलरेडी पता है बस उस एड्रेस पे जाना है और वैल्यू को लेके आना है

तो चाहे एरे का साइज 10 हो चाहे एरे का साइज 10 मिलियन हो अगर मैं रो एथ इंडेक्स या फर्स्ट इंडेक्स पे जाके वैल्यू को एक्सेस करना चाह रही हूं तो दैट इज अ कांस्टेंट ऑपरेशन मुझे ऑलरेडी इंडेक्स पता है तो ये सारी की सारी चीजें हमारी कांस्टेंट टाइम कॉम्प्लेक्शन टाइम कॉम्प्लेक्टेड इज बिग ऑफ n अब बिग ऑफ n का ग्राफ हम ऑलरेडी ड्रॉ करके देख चुके हैं कि इस तरीके की अगर स्ट्रेट लाइन निकलती है तो इसे हम बिग ऑफ n कह देते हैं जहां पे जैसे-जैसे हमारा इनपुट साइज इंक्रीज हो रहा है वैसे-वैसे

हमारे नंबर ऑफ ऑपरेशंस इंक्रीज हो रहे हैं अब लीनियर टाइम कॉम्प्लेक्शन देखा जैसे ही हम सारे के सारे एरे एलिमेंट्स को प्रिंट करने के लिए या स्ट्रिंग के सारे कैरेक्टर्स को प्रिंट करने के लिए एक लूप लगाते हैं हैं तो जैसे-जैसे स्ट्रिंग का साइज बढ़ेगा या एरे का साइज बढ़ेगा वैसे-वैसे मेरे नंबर ऑफ ऑपरेशंस भी इंक्रीज होंगे तो ये हमारा लीनियर टाइम कॉम्प्लेक्शन हो गई लीनियर टाइम कॉम्प्लेक्शन इंडेक्स पे जाके फॉर एग्जांपल आई हैव सम वैल्यूज और मुझे किसी वैल्यू थ्री को जाके ढूंढना है तो अगर मैं इसके ऊपर एक लीनियर सर्च लगाऊं यानी मैं

एक-एक करके एक-एक करके सारे इंडेक्सेस पर जाकर देख रही हूं तो मेरी जो फाइनल टाइम टाइम कंपलेक्सिटी क्योंकि अगर मैं सारे इंडेक्स पे जा रही हूं तो वर्स्ट केस में मैं पूरे के पूरे एरे को ट्रैवर्स कर रही हूं और अगर मेरे एरे का साइज यहां पर पांच के इक्वल है तो अगर पांच साइज का इनपुट है तो मतलब मैंने पांच ऑपरेशंस लगाए अगर 1 मिलियन मेरे एरे का साइज होगा तो मतलब मैं 1 मिलियन ऑपरेशंस लगा रही हूंगी और इनका ग्राफ कैसा दिखेगा इनका ग्राफ जनरली एक स्ट्रेट लाइन मुझे दिखाई देगा सो दिस इज

कॉल्ड लीनियर टाइम कॉम्प्लेक्टेड होता है जिसमें एक तो मैंने लूप लगा रखा है एक जगह मैंने बिग ऑफ n का लूप लगा रखा है और दूसरी जगह मैं कोई कांस्टेंट ऑपरेशन परफॉर्म कर रही हूं कुछ भी नॉर्मल सी वैल्यू प्रिंट करने का तो क्या मैं कह सकती हूं कि मेरे लिए यहां पर मैं इस कांस्टेंट वैल्यू को इग्नोर कर दूंगी जब भी मैं फाइनल टाइम कॉम्प्लेक्शन कर रही हूं क्यों क्योंकि हमारे लिए वर्स केस क्या है वर्स केस ये है कि ये लूप बड़ा होगा कांस्टेंट तो हमेशा कांस्टेंट ही रहेगा तो जब हमारे पास मल्टीपल

टाइम कॉम्प्लेक्शन होती है एक सिंगल कोड के अंदर तब हम छोटी कॉम्प्लेक्शन सबसे बड़ी वाली कॉम्प्लेक्शन को लेते हैं और दोनों केसेस में हमें कैसे पता चलेगा बड़े वाली कॉम्प्लेक्शन कौन सी है हम n के लिए वैल्यू अज्यू कर लेते हैं बहुत बड़ी यानी कोई बड़ी सी वैल्यू अज्यू कर लो 10 टू द पा 6 10 टू द पा 7 काफी 10 मिलियन 1 बिलियन इस तरीके की बड़ी वैल्यू अज्यू कर लो हम n को कभी भी छोटा एज्यूम नहीं करते n = 1 n = 5 ऐसे करके टाइम कॉम्प्लेक्शन कभी कैलकुलेट नहीं करनी n

को हमेशा बड़ा इमेजिन करना है तो यहां पे n जब बड़ा होगा तो मतलब यहां पे तो 1 बिलियन हो जाएगा n और वन हमेशा वन ही रहेगा तो मतलब यह वाली टाइम कॉम्प्लेक्टेड टू दिस टाइम कॉम्प्लेक्शन बड़ी होती जाती है वैसे ही टाइम कॉम्प्लेक्शन है मतलब बड़े इनपुट साइज के लिए कोड ज्यादा टाइम लेगा जितना ज्यादा टाइम लेगा कोड उतना ज्यादा वो कम एफिशिएंट है तो बड़ी टाइम कॉम्प्लेक्शन का मतलब होता है खराब टाइम कॉम्प्लेक्शन में बिग ऑफ वन वाला कोड हमेशा बेटर होगा बिग ऑफ n वाले कोड से इसके बाद नेक्स्ट आ जाते

हैं अपनी बिग ऑफ n स् वाली टाइम बिग ऑफ n स् को जनरली हम क्वाड्रेटिक टाइम कॉम्प्लेक्टेड लूप्स के अंदर मिलता है मतलब मैंने एक फॉर लूप लगा दिया और फॉर लूप के अंदर मैंने एक और फॉर लूप लगा दिया यह क्या हो गई यह नेस्टिंग हो गई नेस्टिंग के अंदर जनरली दो बार लूप रन करता है और दोनों बार अगर n टाइम रन कर रहा है तो हमारे पास n स् टाइम कॉम्प्लेक्शन आ जाती है या फिर अगर हम किसी मैट्रिक्स का भी एग्जांपल लें मुझे अगर कोई 2d एरे दिया हुआ है जिसके अंदर

इस तरीके से मेरा साइज़ है लेट्स सपोज आई हैव ऑफ n बा n तो अगर इस 2d एरे को या इस मैट्रिक्स को मुझे पूरा ट्रैवर्स करना है तो पहले n टाइम करेंगे फिर दोबारा n टाइम करेंगे फिर यहां पर भी n टाइम यहां पर भी n टाइम तो टोटल कितने टाइम्स लगेंगे टोटल कितने ऑपरेशंस लगेंगे पूरे को ट्रैवर्स करने के लिए मुझे लगेंगे n ल्ड बा n ऑपरेशंस व्हिच इज इक्वल टू n स् तो जब भी किसी मैट्रिक्स को मुझे पूरा का पूरा ट्रेवल करना होता है तो वहां पर कॉम्प्लेक्शन आती है बिग ऑफ़

n स् के इक्वल या फिर नेस्टेड लूप्स के अंदर आती है वाली टाइम कॉम्प्लेक्शन उसे रिप्रेजेंट करने के लिए हम कुछ इस तरीके का ग्राफ बना सकते हैं दिस इज बिग ऑफ n स् तो जैसे-जैसे ग्राफ में हम ऊपर की तरफ जाते जाते हैं ना हमारी टाइम कॉम्प्लेक्शन खराब होती जाती है नीचे की तरफ कांस्टेंट है मतलब अच्छा है लीनियर है मतलब थोड़ा सा कम अच्छा है और n स् है मतलब अब हम खराब कॉम्प्लेक्टेड कॉमन टाइम कॉम्प्लेक्शन अब लॉग इन देख के बहुत सारे स्टूडेंट्स घबरा जाते हैं कि लॉग क्या आ गया हमने तो

मैथ के अंदर पढ़ा थाल लगदम हम तो कोडिंग करने आए थे हम मैथ क्यों पढ़ रहे हैं बट इफ आई टेल यू जेनुइनली लॉ n इज योर फ्रेंड क्योंकि लॉग n बहुत अच्छी टाइम कॉम्प्लेक्शन होती है जब भी हम प्रैक्टिकली एल्गोरिथम्स लिखने जाते हैं लॉगइन वाली टाइम कॉम्प्लेक्टेड टू लीनियर टाइम कॉम्प्लेक्टेड में हमें लॉगइन की टाइम कॉम्प्लेक्टेड बहुत सुंदर होता जा रहा है अब लॉगइन का एगजैक्टली मतलब क्या होता है टाइम कॉम्प्लेक्शन की टर्म्स में अब लॉगइन वा टाइम कॉम्प्लेक्शन हमें देखने को मिलती है बाइनरी सर्च के अंदर जब भी हम बाइनरी सर्च कर रहे

होते हैं फॉर एग्जांपल वी हैव क्रिएटेडटेड आउट करना है तो बाइनरी सर्च कैसे काम करता है हम अपने सॉर्टेड एरे के अंदर पहले मिड निकाल लेंगे फिर देखेंगे जिस भी टारगेट को मुझे फाइंड आउट करना है क्या ये मेरे मिड से बड़ा है या छोटा है या उसके इक्वल है अब मुझे पता चल रहा है मेरे मिड से मेरा टारगेट बड़ा है मतलब अब मेरा एरे हाफ हो गया इस पूरे एरे को अब हम इग्नोर कर सकते हैं अब मुझे बस राइट हाफ के अंदर अपने टारगेट को सर्च करना है तो एक ही आइट में

मेरा इनपुट साइज हाफ हो गया तो इस पूरे एरे को अब हम इग्नोर कर सकते हैं अब सेकंड हाफ में आ जाते हैं सेकंड हाफ में मिड निकालेंगे लेट्स सपोज हमारा मिड फोर आता है अब दोबारा से फोर को फाइव से कंपेयर करेंगे तो मुझे पता चलेगा कि मेरे फोर से बड़ा है मेरा टारगेट तो यहां पर भी इस एरे के अंदर हम लेफ्ट पार्ट को कंप्लीट हटा देंगे तो दोबारा से मेरा इनपुट साइज हाफ हो गया और फाइनली इसे अगर हमने हटा दिया तो हम इस लास्ट एरे से जब हम अपने टारगेट को कंपेयर

करेंगे तो हमारा टारगेट हमें मिल गया और यहां पर हमारा बाइनरी सर्च कंप्लीट हो गया तो बाइनरी सर्च कैसे काम करता है कि हर एक आइट के अंदर हम अपने इनपुट साइज को हाफ करते चले जाते हैं इट बेसिकली मींस कि अगर हमने एक एरे के साथ स्टार्ट किया और एरे के अंदर अभी एरे का साइज है 100 के इक्वल तो नेक्स्ट आइट एशन में एरे का जो साइज होगा वो 50 हो जाएगा उससे अगले आइट में एरे का साइज 25 हो जाएगा उससे अगले आइट में n का साइज 12 हो जाएगा और इस तरीके

से हम चलते जाएंगे जब तक हमारे पास वर्स्ट केस में फाइनली सिंगल एलिमेंट वाला एरे नहीं आ जाता तो इस तरीके से तो हमारा जो इनपुट साइज है हर बार हाफ होता चला जाता है अब यहां से लॉग का क्या कनेक्शन है बाइनरी सर्च के अंदर लॉग टाइम कॉम्प्लेक्टेड सपोज मेरे पास एक एरे है वन अब इसका साइज मुझे इंक्रीज करना है टू 100 तो बेसिकली वन को क्या कर रहे हैं हम हर बार डबल कर रहे हैं वन को डबल किया तो टू आ गया टू को डबल किया तो नेक्स्ट टाइम हमारे पास क्या

आ जाएगा फोरर आ जाएगा फोर को डबल करेंगे एट आ जाएगा एट को डबल करेंगे 16 आ जाएगा तो बाइनरी सर्च में वैसे तो हाफ होता था पर क्योंकि हम नीचे से ऊपर की तरफ जा रहे हैं तो हम वैल्यूज को डबल करते जाएंगे तो हमें बेसिकली चाहिए कि वन के साथ मैंने शुरुआत की और हर बार मैं इसे डबल कर रही हूं डबल करने का मतलब है टू से मल्टीप्लाई करना तो बार-बार बार-बार इसे टू से हम मल्टीप्लाई करते जा रहे हैं अब कितने टू से मल्टीप्लाई करेंगे लेट्स सपोज हमने इसे x टाइम्स 2

से मल्टीप्लाई किया x टाइम्स 2 से मल्टीप्लाई करने का मतलब होता है कि 2 टू द पावर x हम ले आए तो जब 1 को 2 टू द पावर x से हम मल्टीप्लाई करेंगे तो फाइनल रिजल्ट क्या आना चाहिए फाइनल रिजल्ट हमारे पास 100 आना चाहिए तो यहां से हमारे पास रिलेशन निकल के आता है 2 टू द पावर x = 100 और x की वैल्यू अगर हमें निकालनी है तो मैथ के अंदर हम लॉग लेते हैं यानी x = l ऑफ 100 बेस 2 यहां पे ये 100 क्या था यहां पे ये 100 मेरे

एरे का साइज था यानी n था तो बेसिकली हम कह सकते हैं x = l n यहां पे बेस को इ कर देते हैं x = l n और x क्या था x मेरे नंबर ऑफ ऑपरेशंस थे जो मुझे सारे ऑपरेशंस अपने बाइनरी सर्च के अंदर लगाने पड़ेंगे तो बेसिकली नंबर ऑफ ऑपरेशंस क्या निकल के आते हैं x क्या है x इक्वल टू नंबर ऑफ ऑपरेशंस नंबर ऑफ ऑपरेशंस इज इक्वल टू l n तो यहां से हमारी टाइम कंपलेक्सिटी निकल के आती है बिग ऑफ l n के इक्वल तो बाइनरी सर्च में जब हम l

n लिखते हैं उसका मतलब यह होता है कि हर बार जब हमारा एरे का साइज हाफ होता चला जाएगा तो उस केस में क्या वर्स्ट केस टाइम कॉम्प्लेक्शन आएगी वर्स्ट केस टाइम कॉम्प्लेक्शन विल बी l n मतलब वर्स्ट केस में लॉग एंड नंबर ऑफ ऑपरेशंस को हम परफॉर्म कर रहे होंगे अब वैसे टाइम कॉम्प्लेक्शन करने के लिए इससे ज्यादा हमें लॉग का मैथ्स सीखने की जरूरत नहीं है सिर्फ इतना मैथ काफी है तो अगर ये पार्ट भी आपको समझ में आया है तो मतलब लॉग हमें क्लियर है इतना नॉलेज के साथ हम अपनी टाइम कॉम्प्लेक्शन

को आराम से कैलकुलेट कर सकते हैं और अगर इस पार्ट को समझने में आपको प्रॉब्लम हुई है तो थोड़ा सा हम रिवाइंड करके लेक्चर का ये पार्ट देख सकते हैं बाकी ये जो कैलकुलेशन है ये जनरली इंटरव्यू में आपसे नहीं पूछी जाएगी आपसे फाइनल टाइम कंपलेक्सिटी ही पूछी जाती है तो हम चाहे तो यहां पर याद भी रख सकते हैं कि हमारी बाइनर स सर्च की टाइम कॉम्प्लेक्शन लॉग इन होती है इनफैक्ट अगर हम बैलेंस्ड बीएसटी की भी बात करते हैं जब हमारे पास कोई बैलेंस्ड बीएसटी होता है जब हम उनके अंदर भी सर्च की

टाइम कॉम्प्लेक्शन लॉगइन वाली टाइम कॉम्प्लेन जनरली लॉगइन वाली टाइम कॉम्प्लेक्टेड करें लीनियर से बहुत ज्यादा बेटर है हमारी लॉग एंड टाइम कॉप्लेक्स टी काफी करीब होती है हमारी कांस्टेंट टाइम कॉम्प्लेक्टेड बहुत अच्छा होता है एज कंपेयर्ड टू अ लीनियर कोड यानी अगर मैं लिखूं कि मेरे कोड की टाइम कंपलेक्सिटी l n के इक्वल है दिस इज मच मच बेटर देन ये ग्रेटर देन ग्रेटर देन का साइन नहीं है ये बेटर का साइन है दिस इज मच बेटर दन बिग ऑफ n और वैसे ही अगर मैं लिखूं कि मेरे कोड की टाइम कॉम्प्लेक्शन के इक्वल है

दिस इज मच बेटर दन हैविंग अ कॉम्प्लेक्शन व्हिच इज n स् तो ये वाला कोड बहुत बेटर होगा एंड ये वाला कोड भी बहुत बेटर होगा एज कंपेयर्ड टू दीज कोड्स अब नेक्स्ट जो कॉमन टाइम कंपलेक्सिटी हमें देखने को मिलती है दैट इज़ n लॉगइन n लॉगइन जनरली कहां दिखती है जनरली हमें सॉर्ट ंग के अंदर दिखती है मैक्सिमम केसेस में जहां भी सॉर्ट ंग हो रही होती है वहां एन लॉगइन की ही टाइम कॉम्प्लेक्शन हो रही होती है चाहे आप इनबिल्ट सॉर्ट को यूज़ करो मतलब कई बार जावा के अंदर c+ प के अंदर

या जावास्क्रिप्ट के अंदर हमारे पास सॉर्ट ंग के ऑलरेडी इनबिल्ट फंक्शंस होते हैं उनकी भी टाइम क कंपलेक्सिटी हमें यही अज्यू करनी होती है या अगर हम खुद से मर्ज सॉर्ट लिखें तो भी हमारे पास टाइम कॉम्प्लेक्शन जो टाइम कॉम्प्लेक्टेड इज़ एक्सपो शियल टाइम कॉम्प्लेक्शन टाइम कॉम्प्लेक्शन का मतलब है कि यहां किसी ना किसी तरीके से जनरली ये कहां देखने को मिलती है जनरली ये रिकर्स में देखने को मिलती है जहां पे भी रिकर्स हो रहा है और हमारे एक डिसीजन ट्री बनता है जब भी रिकर्स होता है एक डिसीजन ट्री बनता है कि हम

अभी यहां पे खड़े थे रिकर्स में हमारे पास दो चॉइसेज हैं ये समझने के लिए हमें ऑलरेडी रिकर्स आना चाहिए कोडिंग के अंदर तो हमारे पास रिकर्स है रिकर्स में लेट्स सपोज हम दो डायरेक्शन में जा सकते हैं अब यहां से भी हम क्या कर सकते हैं यहां से भी हम दो डायरेक्शन में जा सकते हैं यहां से भी हम दो डायरेक्शंस में जा सकते हैं यहां से भी हम दो डायरेक्शंस में जा सकते हैं तो रिकर्स के अंदर एक नोड से जितनी नंबर ऑफ ब्रांचेस निकलती हैं वो तो हमारी एक्सपोसिस टाइम कॉम्प्लेक्शन टाइम कॉम्प्लेक्शन

निकल के आती है एक्सपो शियल टाइम कॉम्प्लेक्शन केसेस के अंदर काफी खराब होती है मतलब मतलब ये जनरली ब्रूट फर्स होती है तो अगर इसे मैं ग्राफ पे दिखाऊं तो ग्राफ पे जनरली एक्सपो शियल टाइम कंप्लेस टी कुछ यहां पर आएगी मतलब बिग ऑफ 2 टू द पावर n कुछ यहां पर आएगा व्हिच इज वे वर्स देन n स् मतलब n क कुछ यहां पे आएगा n टू द पावर 4 यहां पे आएगा और 2 टू द पावर n काफी खराब टाइम कॉम्प्लेक्टेड फर्स रिकर्स की टाइम कॉम्प्लेक्शन होती है काफी खराब होती है बहुत सारे

केसेस के अंदर तो इसीलिए हम जनरली डायनेमिक प्रोग्रामिंग को यूज़ करते हैं इस टाइम कॉम्प्लेक्शन को बेटर करने के लिए तो हम मेमोराइजेशन का यूज़ करते हैं हम टेबुलेशन का यूज़ करते हैं वो सब क्यों यूज़ किए जाते हैं वो सारी जो टेक्निक्स है डायनेमिक प्रोग्रामिंग अपने आप में जो एक टेक्नीक है वो इसलिए यूज़ की जाती है ताकि इस खराब टाइम कॉम्प्लेक्टेड कर सकें इसीलिए टेबुलेशन में कई बार टाइम कॉम्प्लेक्शन करते हैं या कुछ-कुछ केसेस में हम लीनियर तक भी लेकर आ पाते हैं अब इसके अलावा यह तो 2 टू द पावर n हो

गया पर अगर कहीं पर आपको दिखाई दे 3 टू द पा n 4 टू द पा n ये सारी की सारी एक्सपो मेंं शियल टाइम कॉम्प्लेक्टेड के अंदर आती है तो जहां पर भी हम इस तरीके की वैल्यूज देखें दिस इज माय एक्सपोसिस टाइम कॉम्लेक्स टी अच्छा इसके अलावा एक और स्पेशल टाइम कॉम्प्लेक्शन से भी खराब होती है कैसे पता चले एक्सपो शियल से भी खराब होती है उसके लिए हम एक एग्जांपल ले लेते हैं लेट्स रिमूव और ऑफ इट लेट्स सपोज एक है हमारे पास टाइम कंपलेक्सिटी 2 टू द पा n इसमें हम n

= 4 ले लेते हैं तो यह क्या होगा यह होगा 2 * 2 * 2 * 2 मतलब 2 टू द पा 4 और दूसरी टाइम कॉम्प्लेक्शन ये जो वैल्यू है ये छोटी होगी एज कंपेयर टू दिस वैल्यू क्योंकि इसके अंदर 4 3 2 मतलब काफी बड़े नंबर्स हैं जो मल्टीप्लाई हो रहे हैं तो इसीलिए n फैक्टोरियल जब हम बड़े n के लिए कंसीडर करते हैं तो एक वर्स टाइम कॉम्प्लेक्शन होती है एज कंपेयर्ड टू एन एक्सपोसिस टाइम कॉम्प्लेक्शन टाइम कॉम्प्लेक्शन कहां देखने को मिलती है जनरली अगर आप परम्यूटेशन कैलकुलेट कर रहे हैं अगर आप

ब्रूट फोर्स मेथड से सारे एक स्ट्रिंग के सारे के सारे पॉसिबल परम्यूटेशन कैलकुलेट करेंगे तो उस केस में हमें n फैक्टोरियल लग सकता है तो वहां n फैक्टोरियल मतलब एक काफी खराब टाइम कॉम्प्लेक्शन हमारे पास आती है तो अगर हमारे पास इन पांच छह टाइम कॉम्प्लेक्टेड है तो मोस्ट ऑफ़ द प्रैक्टिकल केसेस के अंदर हमारे लिए टाइम कॉम्प्लेक्शन कैलकुलेट करना इजी हो जाएगा और एक ग्राफ देख लेते हैं इन सारी चीजों को समरा इज करते हुए तो यह मेरा इनपुट साइज है यहां पे नंबर ऑफ कंप्यूटेशंस है कंप्यूटेशन यानी नंबर ऑफ ऑपरेशंस तो बेसिकली यहां

पे मेरी कांस्टेंट टाइम कॉम्प्लेक्टेड टाइम कॉम्प्लेक्शन भी खराब n स् आ जाती है फिर जो n क्यूब होती है या n टू द पावर 4 होती है जनरली n टू द पावर 4 या n टू द पावर 5 ऐसी टाइम कंपलेक्सिटीज हमें प्रैक्टिकली उतना देखने को नहीं मिलती पर यह सारी ग्राफ के अंदर यहां पे प्लॉट होती है उसके बाद बाद एक्सपो शियल में हम कुछ यहां पर आ जाते हैं और फिर वर्स जो होती है व्हिच इज n फैक्टोरियल वो हमें ग्राफ के जनरली एंड में देखने को मिलती है हां इससे भी खराब हो

सकती हैं टाइम कॉम्प्लेक्शन पर वो प्रैक्टिकल केसेस में हमें उतना ज्यादा देखने को नहीं मिलती अब यह तो हो गई हमारी सारी टाइम कॉम्प्लेक्टेड मतलब टाइम कॉम्प्लेक्शन सेप्ट्स को पढ़ लिया कैसे कैलकुलेट करते हैं वो सारी चीजें कर ली पर इस नॉलेज को कैसे हम प्रैक्टिकली क्वेश्चंस को सॉल्व करते टाइम यूज कर सकते हैं मतलब अगर मैं लीड कोड पे क्वेश्चंस को सॉल्व करने जा रही हूं या मैं कोड फोर्सेस पे क्वेश्चंस को सॉल्व करने जा रही हूं तो कैसे इस नॉलेज को हम प्रॉब्लम सॉल्विंग के टाइम पे अप्लाई कर सकते हैं उसके बारे में

हम अब बात करने वाले हैं अब प्रॉब्लम सॉल्विंग की अगर हम बात करें तो जनरली हमारे पास डिफरेंट डिफरेंट प्लेटफॉर्म्स होते हैं आप में से कोई स्टूडेंट हो सकता है हैकर अर्थ के ऊपर जाके कोड कर रहा हो कोई स्टूडेंट हो सकता है लीड कोड पे कोड कर रहा हो कोई स्टूडेंट हो सकता है कोड फोर्सेस कोड शेफ के ऊपर जाके कोड कर रहा हो पर जनरली फॉर मोस्ट ऑफ द प्लेटफॉर्म्स हम अजूम करते हैं कि एक सेकंड के अंदर जनरली अराउंड 10 टू द पावर 8 ऑपरेशंस परफॉर्म हो सकते हैं यह हमें अजमन लेके

चलनी होती है कि 10 टू द पावर 8 ऑपरेशंस होने में जनरली एक सेकंड का टाइम लगता है और हमें ये अज्यू करके चलना होता है कि हमारी जो जनरली टाइम लिमिट दी जाती है द टाइम लिमिट दैट इज गिवन टू अस दैट इज अराउंड वन सेकंड कि एक सवाल को हमारे जो रन टाइम लगना चाहिए हमारे कोड को दैट शुड बी इक्वल टू 1 सेकंड इन द वर्स्ट केस सिनेरियो इसका मतलब है कोई भी कोड अगर हम लिखेंगे तो उसमें एट मोस्ट वर्स्ट केस सिनेरियो में हमारा जो कोड है उसके अंदर कितने ऑपरेशंस परफॉर्म

हो सकते हैं उसके अंदर 10 टू द पावर 8 ऑपरेशंस परफॉर्म हो सकते हैं क्यों क्योंकि हमें वन सेकंड ही अलाउड है ये हमें अज्यू करके चलना होता है एंड मैक्सिमम प्लेटफॉर्म्स के ऊपर आप देखोगे कि ये चीज कंप्लीट होल्ड करती है अब मुझे पता चल गया मेरा जो कोड है या मेरी जो एल्गोरिथम है जिसे मैं लिखने वाली हूं किसी भी क्वेश्चन को सॉल्व करने के लिए चाहे वो इजी लेवल क्वेश्चन हो मीडियम लेवल क्वेश्चन हो हार्ड लेवल क्वेश्चन हो उसे सॉल्व करने के लिए मेरा जो कोड है वर्स्ट केस सिनेरियो में उसमें 10

टू द पावर 8 ऑपरेशंस परफॉर्म होने चाहिए तो जनरली हर क्वेश्चन के नीचे कुछ कुछ कंस्ट्रेंट्स दिए जाते हैं इसका एक हम एग्जांपल ले लेते हैं अब लेट्स सपोज हम लीड कोड पर गए और ये ग्रीडी का एक काफी क्लासिकल क्वेश्चन है इसको हमने खोल लिया तो यहां पर इस क्वेश्चन के अंदर मुझे तीन अरेज दिए हुए हैं स्टार्ट टाइम एंड टाइम एंड प्रॉफिट अब तीनों अरेज के लिए लास्ट में जनरली हर बार क्वेश्चंस के लास्ट में हमें कुछ कंस्ट्रेंट्स दिए जाते हैं और अगर इंटरव्यू में आपको डायरेक्टली कंस्ट्रेंट्स नहीं दिए गए तो आप अपने

इंटरव्यूअर से पूछ भी सकते हैं इफ दे आर डायरेक्टली आस्किंग यूर डीएसए क्वेश्चन कि इस वैल्यू के यानी ये जो एरे है ये जो स्ट्रिंग है या जो भी डेटा स्ट्रक्चर आपको मिल रहा है उसके फाइनल कंस्ट्रेंट्स क्या होने वाले हैं तो यहां पे एरे के जो कंस्ट्रेंट्स हैं उसमें दिया हुआ है कि मैक्सिमम साइज एरे का जा सकता है 5 * 10 ^ 4 तो बेसिकली यहां ये मेरे n की लार्जेस्ट वैल्यू हो सकती है तो कैसे इस n की लार्जेस्ट वैल्यू से हम थोड़ा-थोड़ा अजमन ले सकते हैं कि हमारे फाइनल कोड की टाइम

कॉम्प्लेक्शन कॉन्सेप्ट्स को एक बार रिवाइज करते हैं हमें ऑलरेडी पता है कि हमारे सॉल्यूशन में हम मैक्सिमम 10 टू द पावर 8 ऑपरेशंस कर सकते हैं अब अगर कहीं भी हमें कंस्ट्रेंट्स कुछ ऐसे दिए जाए जिसमें हमारे n की वैल्यू 10 टू टू द पावर 8 से ऊपर जा रही है तो क्या मैं कह सकती हूं अगर मेरे पास एक एरे है जिसमें 10 टू द पावर 8 से ज्यादा नंबर ऑफ एलिमेंट्स हैं तो एक-एक करके एक-एक करके मैं अगर इस एरे को ट्रैवर्स करती हूं तो तो क्या होगी मेरे पास लीनियर टाइम कॉम्लेक्स टी

आएगी पर क्या मेरे कोड के अंदर लीनियर टाइम कॉम्प्लेक्शन ये लीनियर टाइम कॉम्प्लेक्टेड किया तो तब तो 10 टू द पावर 8 से ज्यादा ऑपरेशंस हो जाएंगे जो भी मेरे फाइनल एरे का साइज होगा तो इसीलिए जब भी ये क स्ट्रेन दिया जाता है मेरी फाइनल टाइम कॉम्प्लेक्टेड बी बेटर दन लीनियर यानी वो या तो l n हो सकती है या फिर कांस्टेंट टाइम कॉम्प्लेक्शन में भी हम जा सकते हैं बेसिकली लीनियर से बेटर होनी चाहिए डिपेंडिंग अपॉन कि कितनी बड़ी n की वैल्यू हमें दी जा रही है उसके बाद अगर हमें कभी भी बोला

जाता है कि n की वैल्यू लेसन इक्व ट 10 टू द पावर 8 होनी चाहिए तो उस केस में हम अज्यू कर सकते हैं कि मेरी वर्स्ट केस टाइम कॉम्प्लेक्टेड बी लीनियर हां लीनियर से बेटर हो सकती है हम चाहे तो कांस्टेंट टाइम कंपलेक्सिटी में भी अपने सवाल को सॉल्व कर सकते हैं पर लीनियर से खराब में सॉल्व नहीं कर सकते मतलब यह मेरे कंस्ट्रेंट है और मैं n स् का कोड लिख दूं जिसमें कोई नेस्टेड लूप यूज़ हो रहा है तो उस केस में मेरा कोड गलत हो जाएगा और हमारे पास t ही आ

जाएगा टाइम लिमिट एक्सीडेड तभी आता है जब हमारे नंबर ऑफ ऑपरेशंस एक्सीड कर जाते हैं अलाउड ऑपरेशन से तो इस केस में वर्स्ट सॉल्यूशन भी बिग ऑफ n का होना चाहिए अगर मुझे दिया जाता है n < इक्व 10 ट द पा 6 के अराउंड है तो उस केस में हम अज्यू कर सकते हैं कि हमारा जो फाइनल कोड होगा व n लॉग इन का हो सकता है और ऐसे केसेस में एक और हिंट हमें मिल जाता है एक और हिंट ये मिलता है कि क्योंकि n लगन अलाउड है तो इसका मतलब सॉर्ट भी अलाउड

होगी मतलब अगर मेरे सवाल के अंदर कहीं पर एरे यूज हो रहा है तो इसका मतलब है हम इस एरे को सॉर्ट करके भी एक सॉल्यूशन तक पहुंच सकते हैं तो ये आपको एक हिंट मिलता है जब भी कंस्ट्रेंट्स के अंदर n लॉगइन दिखे एक बार दिमाग में हम ये डाल सकते हैं कि अगर मेरे पास कोई एरे है और कुछ सर्टिंग से रिलेटेड सॉल्यूशन है तो मेरे सॉल्यूशन के अंदर सर्टिंग बिल्कुल अलाउड होगी और जनरली यह चीज़ मुझे ग्रीडी प्रॉब्लम्स के अंदर देखने को मिलती है और जिस प्रॉब्लम को अभी हमने डिस्कस किया दैट

इज़ आल्सो ग्रीडी प्रॉब्लम यहां पे हम n टाइम के बेसिस पे सॉर्ट करते हैं जॉब शेड्यूलिंग का जो प्रॉब्लम है इट इज़ अ वेरी क्लासिकल प्रॉब्लम आपको बिल्कुल जाके सॉल्व करना चाहिए अगर आपने सॉल्व नहीं किया है तो और इसमें भी अगर हम कंस्ट्रेंट्स को ध्यान से देखें बेसिकली कंस्ट्रेंट्स के अंदर इस सवाल में मुझे क्या दिया हुआ है n < = 5 * 10 ^ 4 दिया हुआ है अब यहां पे डिफरेंट डिफरेंट वैल्यूज को फिट करके देख लेते हैं यहां पे फिट करके देखते हैं क्या यहां पे n स् अलाउड होगा n स्

का सॉल्यूशन उसके लिए मुझे क्या करना है सिंपली इस लार्जेस्ट वैल्यू को वर्स्ट केस सिनेरियो के लिए लार्जेस्ट वैल्यू को स्क्वायर करके देख लो 5 का स्क्वायर क्या हो जाएगा 25 हो जाएगा एंड दिस इज गोइंग टू बी 10 टू द पावर 8 तो 25 * 10 टू पा 8 तो क्या है 10 टू पा 8 से बड़ा है मतलब ये सॉल्यूशन बिल्कुल भी एक्सेप्ट नहीं होगा ये गलत सॉल्यूशन हो जाएगा पर वही दूसरी तरफ इफ आई टेक n l n तो ये मेरा एक्सेप्टेबल सॉल्यूशन है और जब भी n l n आ रहा है

हम एक बार सर्टिंग के बारे में सोच सकते हैं और क्योंकि क्योंकि मुझे ऑलरेडी पता है क्वेश्चन ग्रीडी का है और इसमें सर्टिंग लगेगी तो यहां पे n लॉग n का कोई सॉल्यूशन है जिसे मैं सोचने की कोशिश करूंगी हां ओबवियसली अगर किसी क्वेश्चन में हम लीनियर तक भी जा पा रहे हैं या कांस्टेंट सॉल्यूशन भी कर पा रहे हैं तो तो बहुत ही बढ़िया है फिर हमें वो चीज करनी है पर वर्स्ट केस को हमने प्रोटेक्ट कर लिया कि n स् वाला सॉल्यूशन यहां पे नहीं चलेगा मैक्सिमम हम n लॉन की लिमिट को टच

कर सकते हैं तो इस तरीके से टाइम कंपलेक्सिटी की नॉलेज हमें कई बार हेल्प कर देती है अपना पॉसिबल सॉल्यूशन गेस करने के लिए उसके अलावा n लेस = 10 टू द पा 4 है तो यहां पे n स् का सॉल्यूशन चल जाएगा क्योंकि n स् के सॉल्यूशन के लिए क्या होगा 10 टू पा 4 * 2 दिस इज गोइंग टू बी 10 टू द पावर 8 मतलब n स् एक्सेप्टेबल होगा पर अगर 10 टू द पा 4 से कोई भी बड़ा कंस्ट्रेंट है जैसे यहां पे 10 टू द पा 4 से एक बड़ा कंस्ट्रेंट

था तो वहां पे n स् एक्सेप्टेबल नहीं होगा वहां हमें n l n की डायरेक्शन में देखना पड़ेगा तो अगर आपको कभी भी ये भी दिखता है n < 10 टू पा 5 तो यहां पर भी हम n l n के बारे में सोचेंगे n स् के बारे में नहीं सोचेंगे अगर हमें कहीं भी मिलता है n < = 500 मतलब जितनी छोटी हमारी n की वैल्यू जा रही है उतना बड़ा एक्सपेक्टेड टाइम कॉम्प्लेक्शन n क्यूब वाली टाइप कॉप्लेक्स टी एक्सपेक्टेड हो सकती है n < = 25 के लिए यहां पे क्या होगा यहां पे

एक्सपो शियल टाइम कॉम्प्लेक्शन हम एक्सपेक्ट कर सकते हैं वो 2 टू द पावर n भी हो सकती है वो 3 टू द पावर n भी हो सकती है पर बेसिक ये है एक्सपोसिस टाइम कॉम्प्लेक्शन टाइम कॉम्प्लेक्टेड हो वहां हम सोच सकते हैं इट माइट बी अ ब्रूट फोर्स रिकर्ट सॉल्यूशन क्योंकि रिकर्स के अंदर जनरली एक्सपो एंजियल हमें देखने को मिलती है और ऐसे केसेस में हम ये सोच सकते हैं कि हमें ज्यादा कुछ ऑप्टिमाइजेशन करने की जरूरत नहीं है क्योंकि जनरली इस सवाल को सॉल्व करने के लिए जो फर्स्ट अप्रोच हमारे दिमाग में हिट कर

रही है जनरली वही सॉल्यूशन होता है तो ऐसी जो कंस्ट्रेंट्स होते हैं उस केस में ब्रूट फोर्स सॉल्यूशन जनरली एक्सेप्ट हो जाता है अब ये जो सारी की सारी हम अंश की बात कर रहे हैं यह हमेशा याद रखना ये सारी अंश हैं ये हर एक सिंगल केस में अप्लाई नहीं करेंगी पर ये काफी जगह अप्लाई कर जाएंगी और वहां पर हमें हेल्प मिल रही होगी इसके अलावा एक n < = 12 वाली टाइम कॉम्लेक्स टी होती है इस केस में हम अज्यू कर सकते हैं कि n फैक्टोरियल की हमसे अजमन है कि कुछ ना

कुछ n फैक्टोरियल टाइप टाइम कॉम्प्लेक्शन n = 12 के लिए n 10 टू द पावर 8 को एक्सीड करता है तो 12 से कम वैल्यू उसके लिए n फैक्टोरियल एक वैलिड नंबर ऑफ ऑपरेशंस हमें करके देगा तो इस तरीके से हम जब भी किसी भी प्रॉब्लम को देखें हम एक उसकी एक्सपेक्टेड टाइम कॉम्प्लेक्टेड टाइम कॉम्प्लेक्टेड इरेक्शन ले सकते हैं कि कौन-कौन से डाटा स्ट्रक्चर्स हैं जिनको यहां पर यूज किया जा सकता है कौन-कौन सी एल्गोरिथम्स हैं जिनको यहां पर यूज किया जा सकता है जब भी लेट्स सपोज हमारा कंस्ट्रेंट बहुत बड़ा दिया हुआ है n

की वैल्यू बहुत बड़ी दी हुई है और यहां पे अगर हम लॉग इन सोच रहे हैं तो तो लॉग इन जब भी हम सोचते हैं हम एक बार बाइनरी सर्च के बारे में जरूर सोचेंगे या अगर हम कांस्टेंट सोच रहे हैं तो कांस्टेंट के केस में हम ये सोच सकते हैं कि क्या पता ये जो पूरा का पूरा मुझे क्वेश्चन दिया हुआ है इसका सॉल्यूशन किसी ट्रिक के अंदर छुपाओ और बिल्कुल एक कांस्टेंट टाइम के अंदर मैं पूरा सॉल्यूशन कैलकुलेट करके निकाल लूं तो इस तरीके से काफी काफी डिफरेंट जो आइडियाज और डिफरेंट जो थॉट्स

होते हैं वो हमारे इमर्ज होकर आते हैं जब हम बहुत सारे एक तो सवालों को सॉल्व कर लेंगे प्लस जब हमारी टाइम कॉम्प्लेक्शन की नॉलेज स्ट्रांग होगी तो टाइम कॉम्प्लेक्शन सिर्फ एक बहुत थोरेट्स के सवाल प्रैक्टिकली हम सॉल्व करने जाते हैं जब सीपी के सवाल जब हम प्रैक्टिकली सॉल्व करने जाते हैं तब टाइम कंपलेक्सिटी की नॉलेज हमारे बहुत काम आ रही होती है प्रैक्टिकल प्रॉब्लम सॉल्विंग करते टाइम तो आई होप कि आज का ये जो सेशन है इसने टाइम कॉप्लेक्स टी से रिलेटेड कुछ नए कॉन्सेप्ट्स आपको सिखाए होंगे जिन्हें हम प्रैक्टिकली जाके अब अप्लाई कर

रहे होंगे एंड कभी भी अगर कोई भी कांसेप्ट हम भूल जाते हैं कभी भी आके इस सेशन को हम रिविजिट कर सकते हैं टू रिफ्रेश आवर मेमोरी टू रिफ्रेश आवर कांसेप्ट और सारे के सारे जो कांसेप्ट होते हैं डीएसए के अंदर वो कहीं ना कहीं एक बेटर सॉफ्टवेयर इंजीनियर हमें बनाने में हेल्प करते हैं तो उस चीज को हमेशा याद रखना है एक लर्निंग पर्सपेक्टिव रखना है जब भी हम चीजों को सीख रहे हैं सारी चीजें थोरेट्स एप्लीकेशन जरूर होता है हो सकता है उस प्रैक्टिकल एप्लीकेशन से अभी तक हम नहीं टकराए हो पर वो

चीज कहीं ना कहीं एजिस्ट जरूर करती है तो आई होप आई वाज एबल टू कंट्रीब्यूट इन योर इंटर्नशिप एंड प्लेसमेंट जर्नी सम हाउ आज के लिए इतना ही मिलते हैं नेक्स्ट वीडियो में चलते कीप लर्निंग एंड कीप एक्सप्लोरिंग