L-2.5: Recurrence Relation [ T(n)= T(n-1) +logn] | Substitution Method | Algorithm

[@KaziMd.RakibulHassan]

For those who are confused when sir wrote the equation n - k = 1, so, k = n -1 if we input the value in the eq then it is become 1 + log2 + log3 + log4+ log5 + ...... as we all know log1=0 if we write, 1+0+ log2 + log3 + log4+ log5 + ......, there is no problem adding a zero in the eq. then we can replace the 0 with log1 simple, now the eq becomes 1+log1+ log2 + log3 + log4+ log5 + ......, which sir wrote in white board so there is actually no problem. Sir did it right....

[@sejalyadav6852]

log 0 will come if we take k=n-1, which is impossible to solve...

[@A2_26_Tushar_kalaskar]

final ans bata, kya hai to

[@himanshushah6746]

He did make the mistake you mentioned but the mistake lead him to add log1(an extra term which should not be added) to the equation. However, it made no difference since log1 is equal to 0 so its like adding an extra 0 to the answer. Please let me know if i am wrong

[@sudhansusekhardaspritam7773]

@@himanshushah6746 wrong question * { 1 if n=0 }

[@FITSOUL01]

Thanks bhai Mera sir phat gaya

[@RiteshKumar-ud7bf]

Sir, at 6:25 when you equate n-k with 1 then k will be n-1 not just 1. And then the whole equation will get changed after 6:57.

[@apexmousham8511]

Answer will be same with same mistake 😳

[@ayushsharma4842]

Yess you are right

[@subhayukumarbala1680]

I too got stuck there thinking it'll be 2 😂

[@gautamgupta7148]

yes you are right but even if we write it that way we can still add 1 in multiplication within logn and answer will be same but yes it should be equal to n-1

[@rahulyo.gaming]

Yaa You Got It Bro 👍😉

[@LearnwithRohit-od1hw]

dear sir here n-k=1 then k will be n-1 and whole equation and question will change at 6:30.

[@lifeandme7360]

At 7:20 of your video....sir n-k=1 n-1=k aayega...not n=k

[@kuldeeptiwari1820]

yeah same i was wondering i am the only on who thought that but still i am getting log 0 in equation which is not possible to solve **edit it will be start from log 2 to log n and time complexity will be same O(n log (n))

[@sarbajitacharjee1195]

T(0)=1 may be the Equation

[@princemaurya3165]

you are right

[@ramijhasanshaik-4177]

TIPS: Take the two conditions as n = 0; n >0; Rest will be fine. Hope it helps you, guys. Love you sir ❤

[@Forthero_J]

Bro, you are saviour 🫡

[@devamshah9649]

no need to do k = n -1 it will be like T(n-k)=T(1) which is 1 so our equation will be as follow 1+log2+log3+log4+......+log(n-1)+log(n) =1+log(2*3*4*5*...(n-1)*n) =1+log(n!) So time complexity will be O(log(n!))

[@pratapsingh-mv3gg]

Happy Teachers' Day Sir. Your explanation style is really eye catching which help us to beat any level of question from any level of concepts. Thank You So much for all of your guidance and support. 🙏

[@pankajpriyadarshy2365]

LOTS OF THANK SIR, I WATCHED YOUR ALL(60) VIDEO OF DAA. I AM VERY GLAD TO SEE THIS. I AM VERY INSPIRED WITH YOUR VIDEO LECTURE AND DECIDE TO DO MCA COURSE. I WISH THAT YOU GUIDE ME. I ALSO WISH THAT YOU UPLOAD ALL VIDEO OF SYLLABUS OF MCA. YOUR EVERY VIDEO GIVE DEEP KNOWLEDGE AND BETTER THAN VIDEO PROVIDED BY UNIVERSITY.

[@atharvanimkar6577]

There is one mistake in given condition everyone should be corrct it.... if n=0 if n>0 This are the correct condition given...👍🏼👍🏼

[@adityasharma2442]

Completed whole playlist today, thank you sir for your efforts, will donate a big amount soon.

[@anugrahmasih6347]

@Anna English I can share but I have done till lecture 17

[@anugrahmasih6347]

@Anna English But I was wondering how are you getting these lectures, these are a mix of both hindi and english ?

[@observantmagic4156]

I will donate after I get placement 😂

[@superblitz2274]

@@anugrahmasih6347 whats there to wonder lol, if you understand both hindi and english, its simple

[@learncseasily3385]

If u have completed the playlist then why are u here ? You should comment this on the last lecture

[@904_arghya8]

I don't know whether you are reading my comment or not, but wishing you Happy Teacher's Day Bhaiya. You are our Bhaiya as well as a teacher. Lots of love and respect for you, for your effort in providing us such a best courses.

[@hafeezaslecturesofcomputer4427]

Pls tell how n-k=1 statment is becomes n=k

[@raunakgupta1475]

No,it is n - k = 0

[@MusicOnTopXHindi]

Approx value is taken as 1000 is approximately equals to 1001 . we cannot find the exact time taken by an algorithm to complete. And also in last we are neglecting constant for finding time complexity. So approx value is taken.

[@ananya88agrawal]

Yes it's k=n+1

[@ganeshkumargupta8614]

@@ananya88agrawal answer mil Jai toh batana 🙂

[@NavendrakumarBanjare]

@@ananya88agrawal k= n-1 😊

[@priyanshisharma8297]

Happy Teacher's day sir may god increase your subscriber day by day. Your way of teaching helps me to clear my concepts also when i solve the question I remember your videos it just makes easy for me to do that. Thanku sir for all your dedication and hardwork.

[@rahulkiteck692]

Where are you from?

[@ryzenae]

Confusion clear, n-k = 1, n = 1 + k k = n - 1 Agar hm n-k = 1 put krke ans. Nikale to ans. Same hi ata hai. 1 + log(n-k+1) + log(n-k+2)........ log(n-3) + log(n-2) + log(n-1) + logn aisa eq.ayega Aur isme *n-k* ko 1 se replace kr do.. To ans. Log(n!) Aa jayega

[@SAKSHISHARMA-ps3sz]

Computer science ka kuch pta hi nhi tha... Itna interest se pdhaya ki hr topic ka pta h ab apse pdhkr

[@utkarshtiwari8590]

I haven't started studying yet, so can you please tell me does this channel has the complete course for GATE?

[@musicandmelody5156]

Happy teacher's day sir. Thank you so much to help us for gaining knowledge.

[@codeattraction2070]

Happy teacher's day 👏👏👏👏 love from Gujarat

[@AnjaliGupta-op1hr]

Happy teacher's day sir✨♥️

[@techkid358]

Sir, at 6:25 when you equate n-k with 1 then k will be n-1 not just 1. And then the whole equation will get changed after 6:57. solution - equate n-k with 0 n-k=0 k=n

[@AshmitKumar-ip9tr]

If agr last tak ka part smjh nhi aaye then what to do please tell

[@rupaleeranjan2783]

Happy teacher's day sir You are the best teacher for CSE students...you work so hard for us Thank you so much ☺️

[@yogeshmishra5658]

don't worry answer is right see explanation n-k=1 k=n-1 T(n)= 1+log(n-(k-1)) +log(n-(k-2)) +log(n-(k-3)) +log(n-(k-4))....................logn T(n)= 1 +log(n-(n-1-1)) +log(n-(n-1-2)) +log(n-(n-1-3))..................logn T(n) = 1 +log2 + log3+ log4+.........logn T(n)= 1+log(2*34*5*6*7*.......................*n) T(n)= 1+log(1*2*34*5*6*7*.......................*n) T(n)= 1+log(n!) T(n)= 1+log(n^n) (how it come see video 8.50) T(n)= 1+nlog(n) 0(nlogn)

[@harshakannake1930]

if we taking log as a common then in bracket it should be 2+3+4+5+6.. isn't it

[@TheMotohead]

I do think the complexity will be log n as the series goes like t(1), log (2), log(3), ……….. log(n)

[@abhishekjain3344]

the number of log terms is not fixed, it will depend on n, that's why the complexity is not logn

[@ReelVibesGram]

Sir you taking the value of n=k which is wrong you take it n=k+1 so we become n-k=1. How it is possible to obtain n=k from n-k=1.

[@ManpreetKaur-in6gz]

Happy teacher's day Sir... 🙏

[@mohammadshahriar5426]

lots of love from Bangladesh.....keep up the good stuff

[@gopalmaheshwari7555]

Sir there is a one minstake at 6.36 min of lac.. Here u had taken a.. n-k= 1:::::: and in the next step u had taken (n=k) Which is wrong... n=k+1 aata h

[@AbhiRaj_37]

Thanks sir

[@puja411]

Happy Teacher's Day Sir 🙏❤😊

[@itzmranonymous]

i have taken n-k =1 and got the same answer .😊

[@adityaanand5927]

Haa in last 1 + n log n - log n and then n log n dominating so order will O(nlogn)

[@SAKSHISHARMA-ps3sz]

Sir apki kya tarif kre plzz ap hi btao...??? Happy teacher day.. Or bhgwan apko hmesha age se age success de.. Or apki family khush rhe

[@alt-f4gaming222]

bhai ek hi dil h kitne bar jitoge......

[@abubakarakhlaq7515]

Happy teacher day Sir! and at 6:25 n=k is wrong as you said n-k=1

[@kanikachouhan6557]

I have a doubt, I think the method you are following is iteration method & subtitution uses mathematical induction. But I too find this method easy & I understood the methodology clearly. Thanks

[@AshmitKumar-ip9tr]

If agr last tak ka part smjh nhi aaye then what to do please tell

[@wisdomdoor7712]

Those who are asking about how k=n , just take n-k=1 then k=n-1 then use it in previous equation so T(n)=T(n-(n-1))+log(n-(n-1-1))+++++log n ; then T(n)=T(1)+log 2+log 3+++++log n ; T(n)=1+ log(2 3 4 5 n) T(n)=1+ log(1 2 3 n) T(n)=log(n!)

[@Abir_Dutta]

Happy Teacher's Day Sir.

[@allahthemostmerciful2706]

Sir u are super duper awesome. I really appreciate your effort and your style of teaching .Really JazakAllah🤍

[@mohitkaushik21]

Thanks sir 😊

[@saptarshibose9718]

sir, it can be done directly with a formula. ! anyway I love your teaching style. I learnt a lot from you. thanks for providing such contents

[@S.A.98]

Which formula ?

[@saptarshibose9718]

@@S.A.98 if problem statement like T(n-1) fx then multiply n with fx. if 2(t-1) fx then 2 power n * fx or 3(t-1) fx then 3 power n multiply fx. or 2(t-1) then 2 power n. and so on...

[@hafeezaslecturesofcomputer4427]

Pls isko sahe tara se explain kre not understanding

[@neerukasaniaparjapati7896]

Happy teacher's Day sir

[@ape1760]

Happy teacher's day sir 🙏

[@VK_BRANDING]

Adv congo for 2 millllllionn !!!!😮❤❤

[@Ap__54]

Sir apne n=k q lia usse to T(0) ho jara , Apko to n-1 =k lena chahiye tha na , tb T(n-(n-1))=T(1)=1 hota . Please 🙏 clarify.

[@pincetoons]

great job

[@sundeepkumar760]

sir, i guess n-k = 1 will give k=n-1....

[@debaratighatak2211]

Happy Teachers' Day sir😊❤

[@farahnisa5475]

After equating n and k, the term T(n-k) should yield zero, won't you agree? If so, then how come it becomes one? To make the term T(n-k) equal to T(1), shouldn't we put the value of k=n-1 so that when its substituted, it becomes: T(n-(n-1))=>T(n-n+1)=>T(1)

[@shubhamsukum]

yeah

[@shubhamsukum]

we put n-k=1 *** -k=-n+1 *** k=n-1. we have to substitute k=n-1 not n.

[@Megh_Jagtap]

It is easy to understand that sir made a mistake. This mistake can be ignored and the answer can be found by taking k=n-1 by our own. Simple.

[@cheena30]

🌸Happy Teacher's Day to u Sir 🌸...Thnk u for your all efforts for us...Ur video lectures help us a lot🙂 Thnk u so much sir for always being there to help in live sessions also 🙃 We will always here to support u✌🏻

[@dharitrisardar3823]

Happy teacher's day 💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐

[@calisthenics-]

Happy teachers day to varun sir 🙏

[@abhishek2107]

Smasher bhaiya zindabad gate fod denge .......is baar lgta hai .

[@anukriti5648]

Happy Teacher's day sir ✨☺️

[@dhananjaykansule3152]

Happy Teacher's day Sir😍

[@Deep_Nature_03]

Happy teacher's day sir ji

[@khabylamefan48]

Happy Teachers day sir❤️

[@nibeditadas4800]

thank you you made day .

[@nithishasaravanan1738]

Happy Teacher's Day Sir :))

[@pankajpriyadarshy2365]

I wish that you upload video of programming language, C++, PYTHON, JAVASCRIPT, HTML. ETC.

[@sahilingale8906]

Thank You SO Much Sir

[@Mridulmishra06]

Sir agar kisi question t(1) =1 wale conditions nhi mention h to kya hum apne man se maan ke solve kr skte hain?

[@vanshgawra6499]

I did it by using n-1 steps instead of k steps and i also got the same answer

[@janakpanchal4376]

n-k=1 So that K=n-1 How can possible sir n=k

[@RohitRayakwar]

Sir please make video on class p and Np completeness .. please sir i am watching your video from my college starting period of time.

[@snehapandey3716]

Sir in this at 7:50 if n-k=1 then k=n-1 ? Right or wrong

[@snehapandey3716]

Sorry At 2:25

[@sumitraina4615]

@@snehapandey3716 yess!! I was wondering the same! And in the end log 1 also won't come but answer will be same in the last....but vo k=n-1 hoga

[@gangadharamdantu9614]

Happy teacher's day to our best teacher.may god bless u with all the happiness and peace in life 💐💐

[@albatablays24]

yhn jo aapny n-k=1 lya hy so eq me wo bhi tw put krskty hy

[@sarthakjain1824]

Nice

[@deepakgautam6904]

6:25 n-k= 1

[@bite091_jamee7]

sir u r great

[@shahinparween3496]

Happy teacher day 🙏🙏

[@ashishkumarsarma5359]

Sir how n-k= 1 became K=n ? It must be n= 1+ k right?

[@kunalmishra4811]

can we take this steps n-1 instead of k?

[@sahilsaraogi5189]

Did you got the answer?

[@husanpreetsingh509]

n-k=1 ,then k=n-1 but you write k= n

[@hafeezaslecturesofcomputer4427]

Me b yehe pooch rahe how it becomes ?

[@learn2know79]

the same confusion is also here.

[@gursewakdhillon8288]

@@hafeezaslecturesofcomputer4427 that was just typo....use your common sense....

[@jaswanthnaik5033]

By mistake n-k=0 it is

[@summaiyalateef5913]

Plz anybody tell me the Answer...As sir took the value wrong at 6:23 as n-k=1 but acc to me...it's K=n-1..💁🏻‍♀️

[@A2_26_Tushar_kalaskar]

tiem complexcity = 0(n^2 logn) , hai kya is it correct

[@atifhassan8098]

sir how to solve recurrence relation by tree method? plz upload video on that

[@RelaxTube_Official]

Sir 6:25 ke baad ghanta nhi kuch samajh aaya... T(n-n) = T(1) kaise hua??? n-k=1 => n=k kaise hua???

[@rahultiwary4257]

Happy Teacher ''s day

[@Priankadey2011]

If the value of n-k = 1 then how it is possible that the value of k = n?? It has to be k = n-1

[@vanditasharma368]

if possible teach us DIP AND CLOUD

[@sayandatta389]

Question is wrong..... if n=0 & n>0 then n-k=0 => k=n

[@anurag3150]

I agree

[@adddddi781]

n-k=1 then k=n-1?

[@kaymylon9711]

6:32............if n-k=1 then how come n=k................it's blowing my mind

[@mohammadanassheikh1446]

KING

[@AshmitKumar-ip9tr]

If agr last tak ka part smjh nhi aaye then what to do please tell

[@IAMLEO-hb4zb]

n-n=0 why it was assume that 1 ,example 5-5=0 not 1

[@devenpatel4684]

If n-k =1 So n =k-1 nai?

[@sambhavgupta1203]

happy teachers day

[@sratnamanjari244]

Happy Teacher's day to Our Varun Sir and Naina Mam ..... 🙏.... Thanku Mam and Sir for all your efforts,hardwork,knowledge, dedication and guidance....You are my inspiration Sir 🙏 ...Need your blessings Mam and Sir 🙏

[@RASmi-s_CREATION]

at 6:25 k=n-1

[@ravanad4245]

k should be n-1 sir .... and we will still get the same ans... because multiple 1 to anything doesn't gonna change our ans .....here its a mistake

[@Obnoxious_25]

This is easy 😎

[@harshgupta3167]

value of k will be n-1

[@akatachadar2846]

Sir plz add videos for k map also in digital

[@mrkpbhati]

sir n-k = 1 k=n kese aayega ? n-k = 1 n = 1+k hoga i think sir can you explain me k =n

[@AshmitKumar-ip9tr]

If agr last tak ka part smjh nhi aaye then what to do please tell

[@adityatiwari9535]

how it is possible if n-k =1 then k=n how it is possible sir??

[@Banditxam4]

n-k =1 hua to k = n-1 hoga na or am I dumb

[@ManishRaghavLeet]

Is video mei mistakes h n=k? value pr Please correct it sir.

[@S_Bhagat-h3q]

happy teachers day

[@anjaliarya6534]

Actually n = 0 & n> 0. question is slightly wrong

[@swayamawasthi4030]

N-K =1 will be N = K-1 AS N != K. THE EQUATION WILL BE MODIFIED AFTER 6:56

[@SidsAnalysis]

You also written Wrong Right 👉 n = k + 1 and k = n -1