L-2.4: Recurrence Relation [ T(n)= 2T(n/2) +n] | Substitution Method | Algorithm

👉Subscribe to our new channel: / @varunainashots
►Design and Analysis of algorithms (DAA) (Complete Playlist):
• Design and Analysis of...
Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
► Operating System :
• Operating System (Comp...
►Database Management System:
• DBMS (Database Managem...
► Theory of Computation
• TOC(Theory of Computat...
►Artificial Intelligence:
• Artificial Intelligenc...
►Computer Networks (Complete Playlist):
• Computer Networks (Com...
►Computer Architecture (Complete Playlist):
• Computer Organization ...
►Structured Query Language (SQL):
• Structured Query Langu...
►Discrete Mathematics:
• Discrete Mathematics
►Compiler Design:
• Compiler Design (Compl...
►Number System:
• Number system
►Cloud Computing & BIG Data:
• Cloud Computing & BIG ...
►Software Engineering:
• Software Engineering
►Data Structure:
• Data Structure
►Graph Theory:
• Graph Theory
►Programming in C:
• C Programming
►Digital Logic:
• Digital Logic (Complet...
---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
► Subscribe to us on KZbin: / gatesmashers
►Subscribe to our new channel: / @varunainashots
► Like our page on Facebook: / gatesmashers
► Follow us on Instagram: / gate.smashers
► Follow us on Instagram: / varunainashots
► Follow us on Telegram: t.me/gatesmash...
► Follow us on Threads: www.threads.ne...
--------------------------------------------------------------------------------------------------------------------------------------
►For Any Query, Suggestion or notes contribution:
Email us at: [e-mail]

[@khushigandhi7322]

This channel needs more recognition and reach! Amazing work!

[@abhinay552]

Hi

[@Smartcity3184]

First for 2^2T( 2(n/2^3) ×n/4) +2n we need to multiply 4 × above whole bracket equation then we have the value of 2^3T((n/2^3)× 4n/4) +2n After divided 4n/4 we got n then add n +2n = 3n After that we have the equation 2^3T(n/2^3)+3n

[@Smartcity3184]

Code with Ayush

[@devpatel1298]

Thanks sir, Aaj me phone leke gaya tha Exam hall me aur ye question aagaya 😂 Course: B.E (IT Branch)

[@AroojArmy]

sir u made a mistake on 3:39 when 2^2 is cancel by 2 how it is still 2^2 i mean the ans should be 2 just........................

[@xenonudaykhandare2836]

bro multiply 2 with bracket... you will get 4T(T/4)+2n/2 and in next step take 4 as 2^2... got it..!!!

[@Archana-j1w2f]

Thanks bhai​@@xenonudaykhandare2836

[@Drakeagarwal]

Bro you all are so dumb , 1st class child can understand that

[@Micbutch]

@@xenonudaykhandare2836 thanks for solving this

[@nabilmalik5042]

Dear teacher, I wish you a happy teacher's day. Thank you for being the guide and for inspiring me to do well in my studies. You are the best teacher HApPy tEaCheR'$ dAy

[@mdtalhashaikh7650]

love you sir, The way of your explanation is too good

[@SAKSHIKUMARIP]

god bless you sir...most useful one!!!

[@silverfanggaming3318]

You are life saver sir...🫡 College exam k end time pe aap ki videos he kam aate hai. You are Life saver for all engineering community. Thank you sir.🫡🫡🫡🫡🫡

[@amaanullah13]

Sir bhot Bdhya samjhaya aapne Glad that I found this channel before time.

[@amitgoswami7856]

Sir congratulations to complete 6lakh subscriber

[@DineshSingh-hx5kw]

Owsm sir...keep doing this we extremely need this❣

[@akshayavbca6704]

honestly my savior , you're the best fam , you always keep things simple. love your videos keep doing 'em

[@tanzidfardin5946]

Nah man U deserve love. really grateful my frnd u just made it simple

[@aamirdehngal2280]

Bhai Allah aapku himmat de 6 lakh sus.but 8 hours views only 800 ❤️❤️❤️

[@shaniabalkhi8065]

Awesome explanation! You just gained another subscriber!

[@empathetic24671]

Very well explained. Mujhe yeh video lagatar 3 baar dekhne pada par mera concept clear ho gaaya. Thank you very much sir!

[@jyeshnupaturi9784]

You are amazing!! Btw it will be great if you could include step count method, tabular method for calculating time complexity of an algorithm and also PRAM algorithms, string matching algorithms too

[@romanasalim5335]

So what is the difference between iterative and substitution method in this qtn sir?

[@dressbydeen]

The way sir says subscribe bahut zaroori hai Hits hard more than time complexity 2 ki power n

[@akashpb4179]

Srji apney college ke prof se zyada toh idhar acha samajh aa rha hai ... koi bhi stepwise explain nahi karta itna clearly kahi bhi

[@meetshah9510]

Beta Dil se padhate he iss liye padho padho

[@Homiechef7]

you're taking it in complicated way my college teacher explains it in very simple and easy way

[@Abc-dk8cl]

Sir good work 👏. Achi Tara samajh ahi ha..

[@shwetankjoshi3011]

Every one make sure u like every one of sir's vdo other wise u will forget this in ur exam

[@kaushikpubg5387]

Sir your explanation and you both are outstanding

[@067-subhannitasaha8]

Hi VARUN SIR ! HOPE YOU ARE DOING GREAT 😃 I have one confusion if = 2 ( 2T (n/4) + n/2 ) + n [ IN THIS STEP HOW YOU HAVE CUTTED THE VALUE 2 OF n/2 and the outer 2 ( i.e. outside the bracket ) = 2^2T ( n/2^2 + n/2 + n) = 2^2T ( n/2^2 + 2n ) HOW IS THIS POSSIBLE BEACAUSE YOU ALREADY CUTTED THE VALUE 2 FROM THE FIRST LINE I HAVE MENTIONED... PLEASE CLEAR OUT THIS DOUBT

[@travelwithme4128]

He did Right check you again , he just multiply 2*n/2 and here 2 is cancle out

[@sahilmusicsss]

same ques

[@raksharthjangid7506]

the first 2 is multiplied individually inside the bracket. [ 2(2T(n/4)) ] + [ 2*n/2 ]

[@jeetmallick508]

Bhai mereko bhi ye doubt hua tha. Dobara uss line ka calculation karo individually. Hojaeyga.

[@sjsjdfe3332]

I also had this doubt

[@maheshupadhyay52]

We are multiply by 2 on both equation sir ne jo karaya hai vo sahi h

[@rajarshimandal3235]

Missing the old board😌

[@AbhiShek.PandwaR]

Great Explanation 😊😊 Keep it up ❤️💙

[@ishitapaneru5023]

Thank you so much sir 💗☺️

[@ihsankhattakofficial154]

Best Teacher ever.

[@vikrantprashantgurav9811]

Sir you are an absolute legend

[@zeeshanfarooq4204]

Congo sir 600k Love from pak ❤️

[@KHALDANASREEN-uf7bl]

you are very very very good teacher 😊and looking like 😍😎❤

[@hrishidev742rdx]

how 2^2T is possible if you cut n/2 by outside 2 then their is only one 2 is left. If you multiply both then 2^2 is ok but you cut it.

[@SunTzuTzu-xr9jv]

Sir, English version of your Lectures. Very great content ❤❤❤❤❤❤❤❤❤❤❤❤❤❤

[@InformationRealistic_str]

sir i am facing difficulty in substitution method and iterative method because the method that u use is same as our teacher taught in iterative method . so what is main difference between them can you help me

[@InformationRealistic_str]

Sir guide and help my DAA Paper is on monday 14 april

[@aneesshahzad3082]

2 ( 2T (n/4) + n/2 ) + n [ IN THIS STEP YOU MULTIPLY 2( 2T (n/4) + n/2 ) SO [2^2T(n/4)+2^(n/2)] + n [NOW IN THIS STEP CUTTED THE VALUE OF 2 IN THE FOLLOW EQ 2^(n/2) AND THE FINAL RESULTS OF THE GIVEN STEP IS 2^2T(n/2^2) +n+n => 2^2T(n/2^2) + 2n

[@mummykdhaba]

2 ki multiple kar di andar n se toh 2n upon 2 hogya fir 2 cancel hogya bacha n +n

[@kalashsoni5072]

sir aap hi engg ki naiyaa paar lagaoge 🤩

[@sushankbais4702]

LORD SPOTTED 🛐🗿

[@AnjuKumari-ft6qk]

Awesome explanation

[@afrinmomin9594]

Hello Sir, Answer is T(n)=n+nlogn then how it become O(nlogn). It should be Ω(nlogn), isnt'it?

[@ashokrajpurohit3671]

Acha smjate ho🔥

[@Harpreetkaur-fd5fu]

Happy Teacher's day sir 🙏✨💫

[@snehadhulap5377]

Sir muzhe mathematical induction and recursion ka lec chaiye tha ..video send kro na ap

[@moonedCake]

Love the explanation ❤ No doubt you are a great teacher 🙏🏼 But, Lord knows who edits these videos! Reminding every other minute "subscribing" the channel is so annoying.

[@mamtadhalla2718]

sir pls explain recurrence relation by iteration of second order equation

[@audiozen2910]

i have a doubt : on 3rd line of answer we eliminated the outside 2 with n/2 then how come on fourth line we have 2^2

[@world_of_programming9653]

Sir how we cancel outer 2 with inner n/2 in 1st two equ's substitution. Coz outer 2 multiplied by all values.

[@tahreemabdulqayyum8424]

Same question sir

[@srishtishrivastava8818]

2 is cancelled in multiplication with n/2 not in overall bracket after being multiplied by 2T(n/4).

[@rahmanuddin184]

Same question plz sir

[@parthbatta7968]

you first do 2 x 2T(n/4) making it 2^2 T(n/4) then we do 2 x (n/2) which cancels 2.

[@thedemonlord300]

@@parthbatta7968 thanks!

[@takshakno7737]

sir just a doubt , why do we always take log both side always , i never understood this , 7:29 plz reply fast ...

[@zainwasem]

Insane so good❤

[@sobiarani2359]

Great sr

[@hisham6899]

if you made these videos in english, it will be a great help to south indians who doesnt understand hindi.

[@aartimashram6859]

Thanku sir❣️

[@SaifUllahArshad-os8qu]

hats of ustad g 🫡💯

[@Lokesh_yadav__]

Finally digital board😌

[@Alan_christo]

Thank you sir

[@SILENT_4_M_6551]

Sir please upload AI and ML playlist Please 🙏🙏🙏

[@Dimpledurgathenepalli]

In 3:28 if we write 2 square there, then how can we cancel the above 2 with 2 in n/2 in 3:37

[@jies933]

Best

[@ashni4932]

Sir please do videos in english also 🙏

[@sahilpatil5445]

1:00 aur device is suscribe kara doo...Chad moment 😎😂

[@souvikbasak4396]

This relation is of which sort technique?

[@aryanbatra5335]

HAPPY TEACHERS DAY SIR!

[@archanaverma3344]

Tq so much sir

[@sreepornasikdarsikdar6184]

I think there is some mistake in the solution..if you are cancelling outer 2 with n/2 then how again you got that 2^2 ?

[@LokeshKumar-jg8md]

Can we call this as iteration method??

[@bunty_98technical4]

2-way Merge Sort ka recursive equation

[@MehndiDesignCollections]

Sir computer vacancy ke preparation hoge kya

[@talhariazx786]

there is a mistake in the step where you cut 2*2 by 4

[@AnimeBoy12377]

Sir agar n ke badle cn raha ga to kuch change ho ga kya

[@Nuur_Rajput]

How can i solve T(n)=T(n/4)+T(n/2)+n² using recursion tree method

[@teekshanheeragcet--]

ye n/2k kaise =1 daal skte ho marzi se

[@anjalicharak2023]

How can u divide 2 and n/2

[@albatablays24]

yeh 2 square or 2 cube khn se aarha hy?

[@amanjain0842]

if i do this same question using Master method then the answer is O(n) . why ?

[@learncseasily3385]

Because u done mistake

[@himankgaming7555]

that was the time complexity for merge sort

[@radhamadhabpanda941]

Sir 2 square kahna se aya uspe

[@saifahmed9152]

bhai shuru ki beat ka link bhej de, rap karna hai uspe

[@janhaviraj5924]

2 square kaise aaya?

[@soumikadey8260]

❤🔥

[@s.maazullah376]

there's a mistake, where's the extra 2 coming from

[@scorpionkingcr4523]

Sir can you please make a video on following equation. 8T(n/2)+n^2 here T(1)=1. Plz sir after 15 days I have exams and this question is important 🙏

[@akashprajapati2636]

Bhai n/2 karke solve karta chala ja aa jayega

[@abdventures]

15 din me ek question toh khud se solve kar le bhai ab toh 1 sal ho gye hue kya??

[@randomvideos979]

[@anshul8415]

For k time it become T(n/2^k + kn) 🧠

[@azmeerasai2005]

By solving this question you did back substitution method wrong check it once.

[@egames1877]

yra equation kay numbers peh circle to karo sara time us peh stuck rha

[@shivanisingh-ix9qm]

👍

[@malikahsan4053]

Sir log ki base u hi nai ati es ye ati ha jab log n ko log 2 se divide krtey han tab ati ha Verna normally 10 hi hoti ha😁🤪

[@saadbinghaffar2269]

can anyone plese tell where these n^2 and n^3 are coming from plz

[@anjalicharak2023]

Where did T go in 4th step

[@priyankarathour6222]

Sir please solve this question by reccurance relations by substitution method an= an-1 +n× 3 power n where a not =1

[@realtopg]

Like here if you don't understand hindi but this be your only option🤣

[@lord_yzal]

completed

[@Rinal-fv8ty]

if anyone can solve it for T(n) = T (n/2) + n. It would be great.

[@anjalicharak2023]

And where didn T go

[@chaitanyarawat7538]

Sir n log(n) Dominating kaise hoga.... For ex: 9 > 9log(9)

[@rukshanaaly7794]

I wish there is english subtitles for this sir :(

[@glazefrect1337]

There are...

[@vinaykumar-ud7rh]

sir 2 ko bracket open kr ke 2t se multiply kr raha ha fir n\2 se usko cancel kasa kr raha ho

[@rutikpatil6758]

By bodmas first solve bracket you have to first multiple 2T by 2 so that it became 2 [4T (n/4) + n] /2 this how it is cut outer 2 by deninometer 2 2 [ 2T (n/4) + n/2] + n 2 [ 4T (n/4) +n ] / 2 + n

[@Unique_demon07]

thanks

[@meenakumar8779]

🙏🙏🙏🙏🙏👍👍👍👍👍

[@NITESHKUMAR-sp6qj]

sir 2 sqaure kaise hua isme

[@MikasaAckerman-oz1hd]

2 already tha ak or 2 aya isliye