लोग जी कैसो सारे दिस लव वबन वेलकम टो चैनल कोड हेल्प सोच लेक्शन बात करने वाले टाइम एंड स्पेस कंप्लेक्शिटी के बारे में एक लेक्शन ऑलरी टाइम और स्पेस कंप्लेक्शिटी डिस्कस कर चुके हैं जहां पर हमने आईटरेटिव प्रोग्राम की तो वो हम इस lecture में समझने वाले हैं, iterative वाली game तो हमें पहले से ही clear है, एक बार आपको थोड़ा से advice करवाएगा, ताकि आपको याद आजा कि हाँ ऐसा कुछ किया था, और उसके बाद हम आगे बढ़ जाएंगे हमारे recursive algorithm के time and space complexity को, और फिर homework के अंदर हमने last 10 day recursion challenge किया था, उसमें जो question solve किये गए हैं, उस question की, उस solution की time and space complexity हम निकाल के, comment में paste करेंगे, या फिर, बताएंगे कि भाईया मेरे को निकालना आ चुका है ठीक है तो यह बात मैं सुझ में आ गई है एक बार शुरू करते हैं बढ़िया से हमने बात करी किसी एग्जाम्पल की हमने बोला लेनियर सर्च में क्या था हमें इतना यादा है यार कि जैसे ऐसे लिखा हमने क्या बोला for एक loop चलाया हमने for int i is equal to 0 से लेके i less than n i plus अगर तुम्हे element मिल जाए यहाँ बताना पड़ेगा ना कौन से element हमने बोला इसका नाम है value हमने बोला if arr of i is equal to value तो इस case में क्या return कर दो इस case में तुम्हें ऐसा करो to return कर दो ठीक है और अगर नहीं तो उस case में तुम false return कर दो ठीक है इस पकार हमने linear search करी थी यार कि जैसे मेरे पास कोई भी array अगर बड़ा हुआ है अगर मेरे पास एक array है ये इस type का तो मैं क्या करता था बहुत simple game थी यार मैं पहले ये check करता था क्या element ये ही है ऐसे में हर एक element पर जाता था linear search के case में तो मैं एक loop चला 0 से लेके index n-1 तक और वापे check कर लिया अगर मुझे value मिल गई तो मैंने true path return कर दिया अगर नहीं मिली तो मैंने false return कर दिया खना तो इस case में हम complexity के इस प्रकार निकाली है कि यार एक loop है जो कि basically क्या कर रहा है 0 से n minus पर index तक चल रहा है अच्छा तो number of comparison कितने हो गई number of comparison तो n हो गई ठीक है तो मैं क्या बोलते था कि इस case के अंदर time complexity जब विकॉ of n आ गई n क्या है और यह एरे का size है या length है जो भी आप कहना चाहें ठीक है space अपने लिए use करी है इस function के द्वारा यहाँ पर space यूज़ हो रही होगी ठीक है फिर मैंने कहा रहा है यह सब तो input है यह सब तो input है इनके जिनता मुझे करने के need नहीं है तो मैंने इसके लिए memory यूज़ करी हुई है तो मैंने कहा बोला है कि constant space यूज़ किया मैंने OO1 बोल दिया हमारी time complexity निकालने के लिए हमारी space complexity निकालने के लिए और इसको detail हम अलड़े पढ़ चुके हैं मैं बोलता नहीं कभी भी आज बोलता हूँ तो सुन लेना So, Nutreschool is an edtech platform जो कि आपके साहिता करने वाले एक full-stack developer बनने में अगले 6 महीने के अंदर इनके एक training program है उसके अंदर क्या करेंगे आपको DAS और जितने भी technical courses required हैं एक developer बनने में और ये guarantee करते हैं आपको at least 5 lakh per annum का package लगवा देंगे तो जब placed हो जाते हैं उसके बाद पैसे देने हैं eligibility criteria क्या है? मैंने बोला कि आप final semester के student हैं या फिर आप fresh grad हैं या फिर एक working professional हैं तो आप apply कर सकते हैं आप join कर सकते हैं मैं CS का नहीं हूँ भईया मैं commerce का हूँ मैं arts का हूँ कोई बात नहीं तब भी चलेगा वहाँ कब है test क्या होगा? एक link description में डाल दूँगा 17 तालिक 17 जनवरी जवाँ last data register करने की वो solve करने और आप apply करने में प्रस्टेस्वल हो जाएंगे कोड्स के अंदर बहुत साइड चीज होने वाले जैसे कि मॉक इंटरव्यूट असाइनमेंट क्विजिस अब हम बात कर रहे हैं recursion की, या फिर हम बात कर रहे हैं recursive algorithms की, ठीक है, तो हमने जब recursion सीखा, हमने सबसे लगते हैं क्या example लिये थे, हमने एक तो factorial वाला example लिया था, कि यह factorial है, और इसको जब हमने recursion समझ लिया था, है न, exponent वाला, हमने counting वाला example लिया था, let's say हम factorial की बात कर रहे हैं, हम factorial की बात कर रहे हैं, let's see, मुझे क्या करना है, मुझे इसकी time complexity निकालनी है, पर यह time complexity होता है क्या, यह तो बता दो, वैसे तो यह चीज आलरेडी हम पुराने वाले lecture में discuss कर चूँगे, अगर आपको नहीं पता, तो आप वाले lecture पहले देखके आएं, उसके बाद यह वाले lecture देखे, अगर मुझे इसको simple शब्द में बताना हो, तो मैंने बोल दिया, it is basically time required as function of जो भी आपने input दिया है, उसका एक function बना देंगे, तो आपने कहा रहा है, it is basically time required as function of your input, जो भी आपने input parameter दिया है, उसके अधार पर आप बता देंगे, कि यार कितना time required होगा इस algorithms, आपको कुछ algorithms compare करनी है आपस में, तो आप time complexity का user compare करते हैं, यार इसकी time complexity अच्छी है, इसकी time complexity गंदी है, ठीक है, दिटेल में time complexity क्या होता है, space complexity क्या होता है, अब हमने short term की बात कर लिखे है, आज basically time required as function of input, right, as function of n, बहुत बढ़िया, ठीक है, तो यह बाता मैं सोच में आ गई अब एक बार मैं अगर factorial code लिखूं तो इस परकार हमने कुछ लिखा था कि यार int factorial हमने इसके अंदर integer भेजा और हमने बोला कि यार base case क्या होगा कि यार जब भी if n is equal to 0 तो इस case में return 1 कर देना बहुत बढ़िया और second हमारा क् फैक्टोरियल ऑफ एन माइनस वन ठीक है तो इस पर ने सिंपल सा कोड लिख लिया था ज्यादा मुश्किल नहीं था बहुत आसान था यह एक हमारा पेस के साथ के ने रिकर्जिव फॉल्ड थी बहुत बढ़िया अब अगर मुझे टाइम कंप्लेक्शन निकालनी लेट से मैंने आपको बोला कि मुझे इस रिकर्जिव फंक्शन की टाइम कंप्लेक्शन निकाल कर दो बताओ मुझे आपने दो लूब होते थे n तक चलने वाले जिरो से लेके तो मैं n स्क्राइब बोलते थे तो इस पर कार्ड करता था पर ये जो है recursive वाला है यहाँ थोड़ा समझ दिया रहा है मैंने बोला कुछ भी नहीं है दोस्त सबसे पहले try करो एक equation लिखने का जो की basically recurrence relation है अगर मुझे किसी भी number का factorial निकालना तो मैं कैसे लिख सकता हूँ कि यार n star factorial of n minus 1 ये लो लिख दिया recurrence relation मैंने बोला बहुत बढ़िया इसको यूज करेंगे अभी थोड़े दिन में यूज करेंगे अब जलते हैं वापस ऊपर ठीक है एक फंडीशन है ना बस, तो मैंने बोला के वन प्लस हो गया बाई, फिर मैंने क्या बोला कि यार देखो यहाँ रिगर्सिव कॉल के अंदर कुछ-कुछ मंटिप्लाई हो रहा है, इसको मैंने बोल दिया के टू, ठीक है यहाँ के टू टाइम लग रहा होगा, बहुत बढ़ हमारा time complexity के लिए एक relation बना लिया, एक setup के लिए relation को, इसको हम जो है, solve करेंगे उमारे time complexity, निकल सकती है, निकल जाएगी या नहीं निकलेगी, बाद बात है, निकल सकती है, ऐसा लग रहा है मुझे, अब मैंने कह बोला है कि इसको तो थोड़ा simplify कर लो, इसको k बोल लो, t of n is equals एन माइनस टू बहुत बढ़िया ऐसे टी ऑफ एन माइनस टू का क्या बनेगा कि टी ऑफ एन माइनस थ्री बहुत बढ़िया इसको ऐसे नीचे ले जाओंगा अगर मैं तो यह क्या हो जाएगा टी ऑफ वन क्या बनेगा के प्लस टी ऑफ जीरो और टी ऑफ जीरो क्या है टी यहां से यहां तक अगर मैं देखूं यहां से आप अगर मैं देखूं तो यह क्या है यह से कट गया यहां से यह से कट जाएगा और आपका बचा गया सिर्फ के बचा हुआ है यहां पर और यह के बचा है और यह टी ऑफ एन बचा है तो हमारा क् एन स्टार के प्लस आपको इसके वन बचा हुआ थी का तो आपका टाइम को प्लेक्सिटी की आ रही है टी ऑफ एन इकॉल्स टू के ए मैंने क्या बोला कि यार ये तो constant है ना इसको neglect कर दो क्या आ गया t of n equals to kn ठीक है मैंने बोला ये तो constant है ना इसको neglect कर दो t of n क्या आ गया n आ गया तो आपकी complexity क्या आ गई big O of n तो अगर आपसे कोई पूछे कि दोस्त factorial है कोई factorial की time complexity बता दो तो आप बोलो के factorial की जो time complexity आईगी यह बास समझ में आई, अब हम से बोचेगा कि भाई factorial की time complexity कैसे निकालो के recursive program की, तो हमें समझ में आ गया, हमने एक relation create कर लिया था, और हमने उसको जो है, यह relation create किया था, उसको हमने बस add up कर दिया, इन सारे sub components को, और हमारा यह answer आ गया था, इसको हमने तोड़ लिया, इसको ह अगर आपको यादो factorial के बाद हमने एक और algorithm पड़ी थी lecture 3 के अंदर, जो कि basically binary search थी, right, binary search, तो binary search का logic अगर आपको याद नहीं तो यह बना देता हूँ, मैंने क्या बोला था कि यार ये एक array होगा, ठीक है, इसमें आपको image element निकालते ���ो, और उसके अधार पर आप देख लेते हो कि यहाँ नहीं जाना, यहाँ जाना है, मतलब एक पार्ट में जाना है, फिर उस पार्ट में जाते थे, फिर एक mid-array में निकालते थे, फिर बोलते थे कि यहाँ नहीं जाना, इस पार्ट में जाना है, तो हर iteration में आपका जो array था, वो ठीक है, बहुत बढ़िया, यहाँ पानी सर्च को निकालो, चलो, lecture number, हम चलते हैं, recursion day 3 पे, यहाँ पर हमने किया हुआ, यहाँ पानी सर्च, ठीक है, code हमको दिख रहा है, कि, इसको थोड़ा साफ सुबा करते हैं, यह अटा देता हूँ, कोई need नहीं है, इसकी भी कोई need नही तो ये मेरा कोई base case है, चलो मैं इसका function बनाना शुरू करता हूँ, मुझे अभी तक यहाँ पर जो मैंने ये वाला part लिखा है, इससे ये समझ में आ गया है कि यार जो मेरा function है ना function, वो किस पर depend करता है, वो कुछ-कुछ processing होती होगी, x, y, z, ठीक है, साथ ही साथ एक function call जाती और यहाँ पर ऐसे mid plus 1 के लिए जा रहे हो थे, यहाँ दोनों में से कोई एक call execute होगी, तो आपका समझ में आगे कि यार ऐसा कुछ-कुछ होने वाला है, कि f के कोई है, कुछ x, y चीज हो रही है, कुछ constant processing हो रही है, और यहाँ पर आप f एक particular array के लिए आप उसके half में जा यह एक base case है इसको मैंने नाम दे दिया के वन कंप्लेक्शिटी कुछ कॉंस्टेंट टाइम कंप्लेक्शिटी लग रही है इसमें प्लस मैंने बोल दी हम कुछ कॉंस्टेंट फिर वाइफ कंडीशन है कुछ हमने मैथेमाटिकल ऑपरेशन करें के टो कंप्लेक्शिटी फिर मैंने बोला यह तो रिकर्जिव कॉल है भाई यह तो मेरे simple कर लिया, इसको मैंने k बोल दिया, तो यह क्या बन गया, t of n is equals to k plus t of n by 2, ठीक है, यह बाता मैं समझ में आ गई यार, ऐसा कुछ-कुछ है, हमने क्या किया, कि यार इसको थोड़ा सा ना और break कर लेते हैं, अगर t of n is equals to k plus t of n by 2 है, तो t of n by 2 क्या होगा, is equals to k plus t of n by 4, t of n by 4 क्या होगा, is equals to k plus t of n by 8, ठीक है ऐसे करते नीचे आ जाएंगे ठीक है कि यार टी ऑफ टू क्या होगा टी ऑफ टू इकल्स टी ऑफ टी ऑ यह इससे कट गया, ऐसे यहाँ एक इससे कट गया होगा, यह कट गया होगा तो at the end यहाँ पर क्या आ गया, t of n is equals to, मैंने कहा बोला कि यहाँ पर क्या बचा हुआ है यहाँ पर अगर आप देखो, तो सिर्फ k बचा है, मैंने बोल तो टोटल ए बार आ रहा है जी आपका के तब का आंसर क्या गया ए स्टार के या गया बटन भी यह नहीं बता कि एक वैल्यू के मैंने कि बला भी निकाल लेते हैं इसको भी निकाल लेते हैं कोई बात नहीं तो मैंने क्या बोला कि यार फिर एंड बाइट फोर साइड करें फिर एंड बाइट फोर साइड कर लिया फिर एंड बाइट साइड कर लिया इसी करते कि हमने बोला कि n upon 2 की power a is equal to 1 होगा और यहाँ से हमने निकाल लिया था कि यार a is equal to log of n आ गया देखिया अगर आपको नहीं समझ मा रहा है कैसे किया ये तो आपने मारी binary search की वीडियो नहीं देखी है उसका title होगा binary search explained ऐसा करके उसमें thumbnail में लिखा होगा तो क्या हो जाएगा t of n equals to k log n ऐसा फिर हमने क्या बोला कि k तो यार constant या neglect कर दो तो क्या हुआ ये log n तो मेरा time complexity क्या आ गई?
मेरा time complexity आ गई O तो आपसे को बोलेगा वो पानी research के recursive implementation के time complexity क्या है? आप लोगे login वो पूछेगा कैसे है? आप लोगे ऐसे है ऐसे निकालेंगे ठीक है? यह कोई चीज है इसमें यह हो सकता है ठीक है? बहुत बढ़िया इसी की ऊपर based एक और algorithm है यार इस प्रति नहीं पड़ता है, मैं इसे बात कर रहा हूं मैंने अगर आपको इस प्रति नहीं पड़ता है, तो इस प्रति नहीं पड़ता है यहां बात करते हैं, अगर हम एक बार ब्लिस डाउन करते हैं तो हम इतना पता है कि एक बार बात बना जाता है अगर हम इस प्रति नहीं पड़ता है, तो हम इस प्रति नहीं पड़ता है यह एक पार्ट है, यह एक पार्ट है तो रिकर्जन इस पार्टों को बदला देता था हम इसके बाद एक नया प्रति बनाते थे उसमें इनको मर्च कर देते थे ठीक है और फिर जो मर्च होकर आया है उस पूरे को हम मेन वाले में कॉपी कर देते थे ठीक है स्टेप्स एक बार लिख जाता हूं आपको याद रह जाएंगे स्टेप्स क्या थे हम सबसे पहले ब्रेक कर देते थे दो एरेज में मैंने ब फिर मैं एक नए आरे निकालता था एक न्यू आरे बनाता था जिसमें इसको मर्च कर देते थे और फिर क्या करता था कॉपी करता था इस न्यू आरे के कंटेंट को किसके अंदर ओरिजिनल आरे के अंदर यही तो करता था मर्च वाट के अंदर मैं यही तो करता था अब मैंन अब मैंने बोला कि मुझे time complexity निकाल करता हूँ merge sort की आपने बोला ठीक है अगर हम code को देखी है हमें कैसे मज़ में आता है merge sort के लिए सबसे पहले हम ये base case जगज़ चेक कर रहे होंगे ठीक है तो मैंने बोला इसकी let's say कुछ constant time complexity होगी k1 चलो कुछ constant time complexity होगी k2 ठीक है चलो फिर मैंने कहा बोला कि हम left part sort करने का try कर रहे हैं अगर full array n size का है यहाँ पर तो left part क्या होगा n by 2 का तो यहाँ पर t of n by 2 आ गया लेफ्ट पार्ट के लिए सेमी सिर्फ अगर हमने यह राइट पार्ट सॉट किया है तो हमने एक और टी ऑफ एनवाइट लिख दिया यह राइट पार्ट के लिए ठीक है फिर मैंने बोला कि इन दोनों को मर्च कर दो मर्च के अंदर दो चीजें थी यार आप एक बार तो आ� के तरह ले लो तो टोटल एंड साइज का सारी मर्च करो ना और फिर आपने कॉपी करा उस पूरे एंटायर आरेजों आपके ओरिजिनल एंड मैंने बोला इसको के फॉर एंड ले लो तो आपने क्या बोला कि यार यह कि थ्री एंड और यह के फॉर एंड ऐसे करके आप जा रहे हैं मैंने बोला कॉंस्टेंट है के लिखे लो ऐसा करो फिर मैंने बोला इसको लो टू ऑफ टू टी एंड बाई टू लिखे के प्लस टू टी एन बाई टू इसको लिए एन के फाइव अब मैंने बोला यह कॉन्शेंट है इसको नेट करते होते हो कोई इशु थोड़ी है तारी लिए टी ऑफ एन इग्ल्स टू टी एन बाई टू प्लस यह एन के फाइव ऐसा करके आपने लिए दिया मैंने लेते हैं मैंने का लिखा कि यार टी ऑफ एन इग्ल्स टू टी ऑफ एन बाई टू अ प्लस एन के फाइफ अब फाइफ लिखने मेरा मन नहीं बार-बार तो मैंने लेट से इसको एन के लिए थोड़ा साफ सुतर लगेगा ठीक है के वन के टू के फाइफ के फोर के लिए दिया क्या हो गया कॉंस्टेंट में चिल मारो कुछ भी लिख दो कुछ फर्क न बाइट लिख देते हैं इसको रिक्वेट आएगा टू टी एन बाइट फूर और यह क्या हो जाएगा एन बाइट टू के बहुत बढ़िया ऐसी आपने लिखा टी ऑफ एन बाई फोर वह क्या हो जाएगा टू टी एन बाई एड और योग या एन बाई फोर के ऐसे करते-करते अब नीचे तक आ गए यार ठीक है यहां पर यहां पर यह जाएगा फोर टी एन बाई फोर प्लस एन के इसी प्रकार यहाँ पर भाईया 4 आ गया, यह तो simple है, मैंने बाता पूरे को 4 चंपलाय कर दो, तो यहाँ पर क्या आ गया, 8T N by 8 plus NK, अगर आप इन पूरे को देखेंगे, तो यह भाईया इससे कट गया, और यह इससे कट गया, तो ऐसे ही सब कुछ कट जाएगा, यहाँ इससे कट जाए तो आप एक टाइम्स है ठीक है त्याद से देखो यह एन की कॉल थी एन बाइट की कॉल थी यह एन बाइट फोर की कॉल थी ऐसे करते आप एन तक आए हैं ठीक है तो इन शॉट एन की कॉल थी एन बाइट फोर की कॉल थी ऐसे करते आप क्या n के कुछ जो है वो इतने times आ रहा है ठीक है यह आपको समझ में आ गया ठीक है अब मैंने क्या बोला कि यार t of n is equal to ठीक है यह तो constant है इसको मैं हटा सकता हूँ तो यह क्या आ गया a n यह है a की value क्या है log n multiply n क्या अंसर आ गया n log n तो मेरी time complexity गो ओफ n log n तो अगर आप से को पूछे मर्ड स्टॉट के टाइम को रिटिटी O of N log N कैसे आ रही है तो आप बता सकते हैं आपके लिए वो चीज बतानी बहुत असान हो चुकी आपको ये सॉल्व करना आ चुका है ठीक है भाईया ऐसे करके निकाल लिया और बाद में एक ही वैल्यू मैंने आप डाल दी ऐसे डन है बहुत बढ़िया ठीक है तो ये चीज आपको समझ में आ चुकी है और हम आगे बढ़ सकते हैं हमारे अगले एक्जांपल के ऊपर मैंने क्या बोला कि हमारा अगला example क्या है हमारा एक्जांपल हमने बोला कि आप फैक्ट कि आप फिबोनाकी सीरीज उठा लेते हैं एक बार फिबोनाकी सीरीज हमने उठा ली मैंने बोला कैसा गोड़ था इसका आपने बोला वह या आसान था कुछ खास मुश्किल तो नहीं तो उस केस में क्या करना था जो भी था वह रिटर्न कर दो और वैसे हम क्या बोलते थे रिटर्न कर दो फिब ऑफ एन माइनस वन प्लस फिब ऑफ एन माइनस टू और यह बंद हो गया भी यह जो था मेरा बेस केस था यह था मेरे रिकर्जिव कॉल था है मैंने कबला टी ऑफ एन इक्वल्स टू इसको मैंने बोल दिया कि आधे कुछ के अ आपको इसको कॉल्ट टाइम दे दो प्लस टी ऑफ एन माइनस टू अब मैंने इसको आगे क्या लिख लिया एन माइनस बन क्या हो गया कि टी ऑफ एन माइनस टू और टी ऑफ एन माइनस थ्री फिर एन माइनस टू निकाला एन माइनस थ्री और ये एन माइनस फूर ऐसे करते जब मेरा टी ऑफ वन तो टी ओफ वन आए टी ओफ जीरो आए दोनों केसे मैं के वन बोलने हुआ था के वन भाई तो मुझे का समझ में आएगा इस पूरे को एडब कर दूं तो क्या होगा य तो यह इससे कट जाएगा ठीक है ऐसे करके यह से कट जाएगा हां ना ऐसे यह कट गया हुआ पर यार यह वाली कॉल तो बच रही है यह वाली कॉल कैसे काटे यह वाला पार्ट समझ में नहीं आ रहा यार तो मैंने बोला ठीक है नहीं समझ में आ रहा है और होगा कि कैसा हो सकता है क्या यह आपके लिए होम वगन मैंने बोला कि चलो हो सकता बट मुश्किल है मैं हमने क्या बोला कि चलो इसका recursion tree बनाते हैं अगर मुझे याद हो तो n के case में call कहा जाएगी n-1 पे जाएगी और n-2 पे जाएगी फिर n-1 के case में कहा जाएगी n-2 पे और n-3 पे ऐसे करते आप कहा तक जाओगे जब तक आपकी 1 या 0 पे नहीं आ जाती call देखिया क्योंकि 1 और 0 हमारे base case है right तो इस पकार हमने यह कुछ-कुछ एक tree बना लिया है और मुझे क्या पता है कि हर एक node जाएगा वो दो node को call करने वाली है योगि अगर ये 3 है तो ये 2 को और 1 को call करेगा 4 है तो एक कम यहाँ और दो कम यहाँ यानि कि 3 तो इस प्रकार call करेगा है ना तो मुझे इतना तो एक idea है अब मैंने क्यों बोला कि मुझे overall time निकालना हो तो मैं किस प्रकार निकाल पाऊँगा अगर मुझे overall इस Fibonacci series वाले function का time complexity निकालनी है तो मैं कैसे निकाल पाऊँगा ठीक है इसको मैं इसे निकाल सकते है मैंने बोला अगर इह हर एक सिंगल नोड अगर इस नोड जो है वह लेट से के टाइम ले रही है इस नोड लेट से के टाइम ले रही है तो आपका टोटल टाइम किसके एकवल आ जाएगा बेसिकली के मल्टीप्लाइट टोटल नोड्स राइट इसके एकवल आ जाएगा बस यह ओवर ऑल टाइम कंप्लेक्शिटी कितनी है तो मुझे कैसे मज़ में आता है कि यार पहले आले केस में एक नोड है पहले लेवल पर दूसरे लेवल में यह दो नोड है इसी प्रकार अगर मैं तीसरे लेवल पर जाऊं तो यार दो बच्चे तो इसके हो गए एक और दो इसके अगर लेवल पे, ऐसे करते हैं, 16, अगर लेवल पे 32, ऐसे बढ़ता जा रहा है, 2 के multiple में, तो आपने कहा बोलो, लास्ट लेवल पे कितने नोड होंगे, 2 की पावर something, अगर मैं ध्यान से देखूं, यह क्या है, यह है 2 की पावर 0, फिर यह क्या है, 2 की पावर 1, 2 की पावर 2 यह पर गया फोर पर गया फिर इस प्रकार यह जाएगा फाइव यह फोर यह थ्री यह टू और यह वन ऐसे करके यह पूरा लंबा यहां तक गया हुआ है बट यहां पर क्या होगा फोर है यह थ्री पर क्या होगा और यह टू गया होगा यह वन पर क्या होगा यहां पर और अच्छे से बनाते हैं इसको यहां पर वन पर क्या होगा और यहां पर जी यहाँ पर जो भी आपका एन है और यह वाली डेप्ट आपकी जो है वह एन बाइट टू है बट हम एजूम कर रहे हैं लेट से हम एजूम करेंगे लास्ट वाले लेवल में इस प्रकार है कि भाई सब के दो बच्चे हैं जब सब के दो बच्चे हैं तो लास्ट वाले रहतूं तो क्या देगा भाई वन प्लस वाले टू से लेकर टू की बार एन तक इस बेसिकली टू की बार एन प्लस वन माइनेस वन ऐसा कुछ आ गया है अब मैंने बोला मेरी overall time complexity क्या है भाईया वो तो हम देख चुके थे अभी basically k multiply 2 की बावर n plus 1 minus 1 मैंने बोला यार node ये जो constant है इसको हटाओ यार फिर क्या बचा k multiply 2 की बावर n plus 1 मैंने बोला कैसे लिए सकता हूँ इसको k multiply 2 की बावर n ये क्या है k multiply 2 की बावर n क्या बचा सिर्फ 2 की बावर n exponential आ गई यार तो इसका मतलब जो मैं Fibonacci वाला function लिखके बैठा हूँ उपर अभी, जस्ट आपने देखा, ये वाला, तो इसके case में time complexity जो है, वो exponential आ रही है, ठीक है, यहाँ पर मैंने देखा था न, यह वाली चीज, कि K multiply total node, तभी मैंने यहाँ पर K multiply total node कर दिया, तो हमारे इस case में exponential time complexity आ रही है, जो कि बहुत ही गटिया होती है, तो यहाँ पर हमने कुछ-कुछ examples देख ली हैं यार, हमने अब तक देख लिया के यार, सबसे पहले में factorial पढ़ा था हमारी recursion series में, तो factorial भाई साहब, हमने complexity निकाल ली, o of n निकाल दी, हमने उसके बारिणी research लिखा, बारिणी complexity हमने o of log n निकाल दी, उसके बाद मट सोटी कम्लेक्शिटी हमने ओ ऑफ एन लॉग एन निकाल दी, उसके बाद हमने फिबर नाकी देखा, फिबर नाकी कम्लेक्शिटी हमने ओ ऑफ बिग ओ ऑफ तोगे वर एन निकाल दी, और यह सारी जो हमने रिकर्जिव कम्लेक्शिटी निकाल ली है, रिकर्जिव और ग्र एक तरीका तो आपको यह वाला आ गया दोस्तों तरीका आपको यह रिकर्जन ट्री वाला भी आ चुका तो यह दो तरीके आपको टाइम को निकालने के आगे यार ठीक है इस प्रकार आप निकाल सकते हैं और भी तरीके होते हैं कुछ थोरम्स भी होते हैं इनका यूज करके हमने बहुत सारे क्वेश्चन किए हैं रिवर्जन में 10 डी सीरीज थी हमारी तो जितने क्वेश्चन पेंडिंग है जितने क्वेश्चन के लिए टाइम क्लिक्सिटी नहीं निकाल लिया है वो सारे क्वेश्चन आपको निकाल लिया ह और ये बहुत सारे MCQs आपको नजर आ रहे होंगे ठीक है तो इन MCQs को भी आपको solve करना है इसमें दोनों के दोनों चीज़े आईटरेटिव वाली time complexity वाले question भी हैं और साथ recursive वाले भी हैं तो आपको code studio पर जाना है आपको ये link description में मिल जाएगा और आप सारे के सारे time बिल्कुल बेसिक से समझने के लिए आपको फिर दो बार पुराने वीडियो देखनी पड़ेगी, हम पहले वो बना चुके हैं, यहाँ पे हम ज़्यादा डेफिनेशन पर डिस्क्यूस नहीं करेंगे, हम सिंपल बोलते हैं यार, बेसिकलेट इस स्पेस रिक्वार्ड ऐसे करके आपका कुछ एक well defined path आपको दिखाता ग्राफ के अंदर, space complexity वाला case थोड़ा different हो सकता है, हो सकता है आपका program जो है वो कुछ भी ऐसे memory use कर रहा हो, और उसके लिए expression निकालना, शायद हमारे लिए थोड़ा मुश्किल हो जाए, ठीक है, ऐसे करके म at any instant of time यहाँ इस ग्राफ के अंदर जो भी maximum space आ रहा है ना वो ही मैं इसकी space complexity दर्शा दूँगा कि यह इतना space मुझे चाहिए किसी भी interval पर ठीक है जैसे इस interval लेट से यह 1 था यह 2 है यह 3 है यह 4 है यह 5 है तो मुझे दिख रहा है मैंने कह बोला कि maximum space required at any instant of time यह maximum है इसको space complexity में दर्शा दूँगा और बस आपका answer आ गया इस प्रकार, so let's say, हम सबसे पहले factorial वाला code ही उठा लेते हैं, factorial वाले code की बात कर लेते हैं, कि यार factorial वाले code की space complexity बता दो कितनी होने वाली है और कैसे निकलने वाली है, हम जाते हैं दोबारा यहाँ पर, हमारे recursion day 1 पर यहाँ पर जाके factorial select कर लेते हैं, हमने code को इस प्रकार ल मेरा कुछ constant space, 2 variable तो बनाए हैं, कुछ constant space ले रहा होगा तो मैंने क्या बोला, कि let's say मैंने 5 का factorial निकाला तो क्या होगा, पहले 5 के लिए call गई होगी फिर 5 के लिए 4 पे call गई होगी, फिर 4 के लिए 3 पे call गई होगी फिर 1 ने answer 1 return किया होगा, फिर इसने 1 star 2 2 return किया होगा, फिर इसने 6 return किया होगा, इसने 24 return किया होगा हर एक function ने ये वाले 2 variable तो बनाई होंगे smaller problem, bigger problem इस code के हिसाब से देखा?
तो आप देखा कुछ constant space तो ये नोड़े लिया हो आए है कुछ k constant space तो ये नोड़े लिया हो आए है तो हमें recursive call stack याद है? तो मैंने क्या किया? function call stack की बात कर रहा हूँ यार main function है इस main function इस factorial वाले function call किया होगा सबसे पहले factorial of 5 call आई होगी ठीक है factorial of 5 फिर उस factorial of 5 ने 4 को call किया होगा ठीक है factorial of 4, ऐसे ही यहाँ पर factorial of 3, ऐसे ही यहाँ पर factorial of 2, ऐसे यहाँ पर factorial of 1, 1 तक हम पहुँच गए, यह तुम्हारा base case आ जाएगा यहाँ पर, तो यहाँ पर ध्यान सा कर देखें, तो इस call stack में इसने कुछ space ले रखा है के, इसने कुछ space ले तो इन शॉट मेरी जो space complexity है वो क्या आ गई k multiply n आ गई मैंने बोला constant है दोस्तों इसको ज़्यादा टेंशन बत ले तो आपकी complexity क्या आ गई big O of n आ गई किसके लिए factorial वाले प्रोग्राम के लिए जब तक ऊपर से सारे function clear नहीं हो जाते, 4, 3, 2, 1, ए सेम 4 आया, 3 आया, 2 आया, 1 आया, जब ये पांचों function यहाँ पड़े हुए हैं, जब ये पांचों के पांचों यहाँ पड़े हुए हैं, इन सबने k memory तो ले ही रखी है, अगर यहाँ पे same factorial of n निकाला होता हो, तो n function call होती अब हम बात करते हैं second question के इसका नाम है binary search आपके सामने यहाँ पर code हमने खोल दिया ठीक है मुझे क्या दिख रहा है भाई मुझे क्या पता है let's say मैंने अगर किसी area के लिए call मारी इसका size n है तो मुझे पता n के लिए call जाएगी फिर n by 2 size के लिए call जाएगी 1 तक call जाएगी ठीक है log n हमने इंकाल दा ना यह पूरी डेट चाहो एटाइम्स है फिर एन बाइट टू की पावर एडिटल टू वन है एडिटल टू लोग ऑफ एन हो गया है ना यह लोग तो आपके रिगरेजन डेप्ट कम कह देते हैं तो मैंने क्या बोला कि यार सबसे पहले क्या हुआ वाला चुका तो सबसे पहले बायने सच कॉल हुआ एन साइज के रेके लिए ठीक है फिर कॉल हुआ होगा एन वाइट टू साइज के रेके लिए ठीक है फिर कॉल होगा एन वाइट फोर साइज के रेके लिए ऐसे कब तक जब तक वन साइज के रेके नहीं आ जाता अब हमें देखना है कि पहला वाला फंक्शन जो है मतलब एक सिंगल फंक्शन को कितनी मेमोरी ले रही है जहां से अगर देखें तो एक मिड है एक मिड कर लिया हमने और इसके अलावत हम कोई बी मेमोरी ले नहीं रहे हैं इसके अलावत कोई ब कि ठीक है और इतनी फंक्शन कॉल है यह ए फंक्शन कॉल है ए टाइम्स एक वैल्यू के लॉग एन है तो आपकी स्पेस कंप्लेक्शिटी क्या आ गई के मल्टीप्लाई लॉग एन यानि के बिग ऑफ लॉग इसको मैं निकलेट कर सकता हूं तो अपने बायरी सर्च की स्पेस कंप्लेक्शिटी भी निकाल ली ठीक है आगे बढ़ेंगे वाले थर्ड अगर दंपर जैसे इस पर देखिए भी मर्श और की बात कर लेते हैं अब हम आगे merge sort के ऊपर मैंने फिर दुबारा merge sort का एक बार function खोल लिया ये था हमारा day 5 पे जहां तक मुझे आता है ठीक है अब यहाँ पर space complexity वाली game देखें नहीं एक बार कि हमने यहाँ पर कितना space acquire किया हुआ है ठीक है मैंने क्या बोला कि मर्ज sort में क्या होता था क न्यू आरिया था ठीक है और फिर इस न्यू आरिया के जो मर्जो कंटेंट है उसको इसमें हम कॉपी कर देते थे हमने ऊपर जस्ट देखा इस चीज को भी है ना ऐसा कुछ करते थे हम तो अगर मुझे इसकी स्पेस कॉम्प्लेक्शिटी निकालनी है मैं कैसे निकालूँगा अगर मैं reality की बात करूँ तो तब से वाले यह आपका एक एरे था starting में इसने इसके left half में call मारी यह sort हो गया यह वापस आ गया फिर right वाले half में call गई यह sort हो गया यह वापस आ गया फिर उसके बाद जो है आपने एक नया एरे बनाया उसमें इन दोनों halves को merge कर दिया और फिर इसको पूरे original आरे में copy कर दिया मैंने बोला कोई बात नहीं आ जाएगा नॉर्मल है चालो अब हमने क्या किया?
ध्यान से एक बर देखते हैं कि सबसे पहले n size के ल फिर यहाँ n by 2 size के लिए call गई है, यहाँ भी n by 2 size के लिए call गई है, फिर यहाँ n by 4 size के लिए call गई है, यहाँ भी n by 4, ऐसे कब तक चलता रहेगा जब तक आपका single size नहीं हो जाता, है न, ऐसा, तब तक, जब तक one size नहीं हो जाता, one के बाद इस प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल भी प्रेमियाल तो यह क्या होगा n, n by 2, n by 4 से लेके 1 तक मैंने पता है कि यह पूरी depth को मैं क्या बोलता हूँ, log n बोलता हूँ तो एक space वाला component तो मुझे सबज में आ गया कि यह एक space वाला component क्या है यह क्या है, k आ रहा है कितनी बार, log n बार तो k, log n मेरा एक component तो आ ही गया, बहुत बढ़िया यह recursion depth वाले concept हमारा आ गया, second मुझे क्या पता था एक new array concept समझाया था तो जो नए आरे आपे create कर रहे हो, code wise अगर आपको मैं दिखाऊं, तो देखो यहाँ पे create के न, left और right के लिए, तो जो new आरे आपे create कर रहो, यहाँ पे भी space आपने लिया यार, यहाँ पे भी आपने space लिया है, तो इस space को भी consider करना पड़ेगा, इस space को भी consider करना पड़ेग फिर हमने बोला कि पहले n by 2 वाला पार्ट सॉर्ट करके लाओ, फिर हमने बोला कि n by 4 वाला पार्ट सॉर्ट करके लाओ, फिर हमने क्या बोला कि 1 वाला पार्ट सॉर्ट करके लाओ, यहां से हम वापस आ गए, लेट से हम n by 4 वाली call पर आ गए, तो जब हम इस n by 4 वाले size को स� तो हमने जो भी size के लिए sort कर रहे हैं, जिससे हमने वो array create किया था, जैसे हमारा यह sorting वाला काम यहाँ पूरा हो जाता था, हम इसको destroy कर देते थे, ठीक है, तो कुछ भी यहाँ पर add up नहीं होने वाला, तो हम यहाँ से उपर गए, तो यहाँ पर जाने से पहले इसको destroy कर दिया अब हम n size पर आ गई, यहाँ पर हमने क्या किया होगा, हमने यहाँ पर n size का एक array बनाया होगा, new, उसको हमने क्या बोला, कि हमने इस logic के द्वारा merge कर दिया, इस logic के द्वारा merge to sorted arrays वाला logic लगा दिया, और फिर इसको destroy कर दिया, और फिर हम वापस चले गए, मैंने क्या बोला तो इस इन शॉट ये मेरा n वाली चीज को मैं यहाँ consider कर लेता हूँ, n, तो मेरी space complexity क्या आ गई, k log n plus n, मैंने क्या बोला, कि यार ये तो k है, और log n तो n के सामने बहुत चोटा होता था, तो इस पूरी term को neglect कर सकता हूँ, है न, क्योंकि n तो बड़ा है भाई log n से, n तो ब� बाया ये वाली चीज समझ में नहीं आई कैसे हुआ मैंने बोला आजाओ इदर अगर आपके n की value 1024 है तो देखो क्या होता अगर आपके वालो n की value 1024 है तो क्या होगा log n क्या हैगा उस case पर 10 हाँ जाएगा है comparable खुदी बताओ ये है 1024 और log n क्या हो जाएगा 10 हाँ जाएगा तो comparable लगता है कहीं से नहीं लगता है ना इसलिए मैं इसको neglect कर पा रहा हूँ तो in short मेरी यहाँ पे complexity क्या आगई space complexity much short O of n आगई यहाँ पर दो component थे यहाँ पर दो component थ तो इसमें जो maximum होगा मैंने consider कर लिया, maximum था n मुझे पता है कि n जो है बहुत बड़ा होता है k log n से, तो मैंने इसको neglect करके, और often मेरा answer आ गया तो ये मेरी space complexity होगी merge sort की ठीक है ये भी आपको अब तक clear हो गई होगी चोथा fifth वाला part ये बाइया fifth वाला समझाओ fifth बनाके series फिब बनाके series बता दो बाइया मैंने बोला ठीक है दोस्ट चलो हमें क्या पता है फिब बनाके series में let's say मुझे 5 के लिए कुछ निकालना तो क्या हो और यहाँ पे 0 में call जाती है ने तो वैसे किसी यहाँ कुछ जाएगा नहीं आर और इसके बाद यहाँ पे 1 और 0 में call जाती है बहुत बढ़िया ऐसा कुछ-कुछ हमारा recursion tree बनता ऐसा कुछ-कुछ हमारा recursion tree बनता बहुत बढ़िया मैंने क्या बोला असलियत में क्या होता 5 के लिए call गई फिर 4 के लिए call जाती फिर 3 के लिए call जाती 5 के लिए call गई फिर 4 के लिए call जाती फिर 2 के लिए कॉल जाती, फिर 1 के लिए कॉल जाती, यह मेरी recursion depth हो गई, यहां से अगर देखें तो, यह मेरी recursion depth हो गई, यह मेरी recursion की depth हो गई, फिर क्या होता, 1 से कॉल वापस आती, फिर यहां जाती, ठीक है, फिर यहां से कॉल वापस आती, फिर यहां जाती, फिर यहां फिर यहां वापस और फिर यहां से वापस इस प्रकार आपकी कॉल चलती तो हम ध्यान से देखें सबसे लंबा पात क्या होता है इस केस के अंदर यह वाला पात हमेशा लंबे होना वाला है हमने अभी थोड़ दर बड़ डिस्कस किया कि यह वाले पात की जो लेंथ होगी रिगरेशन डेप्ट होगी वो एन होगी और यह वाले पात की एन बाई टू होगी मैक्सियम क्या आ रही है किसी भी केस के अंदर यह वाली लेंथ तो अगर मैं function call stack बना दूँ, तो पहला आपका main call हुआ होगा, फिर 5 के लिए call गई होगी, 4 के लिए गई होगी, 3 के लिए गई होगी, ऐसे करते 1 तक गई होगी, और यह हर कोई constant space ले रहा है, constant k space ले रहा है, है ना, और अगर हर कोई constant k space ले रहा है, और total call जो है, वो कि तो हमने आप फिर दोबारा वोई चार प्रगाम दोबारा डिस्कस कर लिये यार, factorial, उसके बाद हमने binary search किया, फिर हमने merge sort किया, और फिर हमने Fibonacci कर लिया, ठीक है, इसके case में, Fibonacci case में O, merge sort case में भी O, binary search case में O, factorial case में O, ये चारो space complexity हमने निकाल लिये, homework क्या भी है, 10 day series के अंदर, वो सारे के सारे question की space complexity, आपको, निकालनी है साथी साथ यह Code Studio का आपको एक पेज नजर आ रहा होगा background में यहाँ पर जाना है और जितने भी questions हैं वो सारे के सारे आपको solve करने हैं इन शॉट आपको अब तक time complexity और space complexity निकालनी आ जानी चाहिए both for iterative programs and recursive programs तो यह चीज़ें आपको अब तक clear हो जानी चाहिए और homework करोगे तो और clear हो जाएंगे देखे हमने यह चार example लिए हैं इसके दूर आपको समझानी कोई इशकी हमें दो चीज़ें अब तक आती है time complexity case म हम वह expression के द्वारा solve कर सकते हैं या फिर हम recursion tree के द्वारा solve कर सकते हैं ये दो चीज़ें हमने सीख लिये space के केसे मुझे क्या पता है कि यार मेरा recursion depth काम आने वाला recursion depth के द्वारा मैं answer निकाल सकता हूँ और देख लूँगा कि और extra additional space कैसे मैं allocate कराने की कोईश कर रहा हूँ उसके और मुझे बताना कैसे लगी वीडियो अच्छी लगी है बेकार लगी है आपसे अगली वीडियो में तब तक के लिए बाई टाइम के और दिखाए तो एक बार दिखावा भी पॉटन है ठीक है 2 बचके 23 मिनट तो रात को शूट करते हैं और बस इस वीडियो में तक मिलते ह