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

[@checkmate0923]

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 👍😉

[@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 🫡

[@LearnwithRohit-od1hw]

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

[@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...👍🏼👍🏼

[@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

[@dopo_orichi]

@@kuldeeptiwari1820 yes i got same starting from log 2 to log n

[@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!))

[@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

[@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. 🙏

[@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?

[@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.

[@shorts_afx]

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

[@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 😊

[@codeattraction2070]

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

[@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

[@mohammadshahriar5426]

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

[@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?

[@AnjaliGupta-op1hr]

Happy teacher's day sir✨♥️

[@musicandmelody5156]

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

[@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!)

[@ManpreetKaur-in6gz]

Happy teacher's day Sir... 🙏

[@rupaleeranjan2783]

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

[@alt-f4gaming222]

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

[@puja411]

Happy Teacher's Day Sir 🙏❤😊

[@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.

[@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

[@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

[@deepakgautam6904]

6:25 n-k= 1

[@allahthemostmerciful2706]

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

[@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)

[@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

[@abhishek2107]

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

[@Abir_Dutta]

Happy Teacher's Day Sir.

[@VK_BRANDING]

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

[@AbhiRaj_37]

Thanks sir

[@ape1760]

Happy teacher's day sir 🙏

[@abubakarakhlaq7515]

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

[@swetakr1269]

Thank you sir 😊

[@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

[@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

[@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

[@bhavanagayathri1347]

Happy teacher's day sir

[@dharitrisardar3823]

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

[@Deep_Nature_03]

Happy teacher's day sir ji

[@dhananjaykansule3152]

Happy Teacher's day Sir😍

[@debaratighatak2211]

Happy Teachers' Day sir😊❤

[@anukriti5648]

Happy Teacher's day sir ✨☺️

[@nithishasaravanan1738]

Happy Teacher's Day Sir :))

[@pankajpriyadarshy2365]

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

[@sundeepkumar760]

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

[@khabylamefan48]

Happy Teachers day sir❤️

[@adddddi781]

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

[@albatablays24]

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

[@nibeditadas4800]

thank you you made day .

[@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.

[@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

[@mohammadanassheikh1446]

KING

[@calisthenics-]

Happy teachers day to varun sir 🙏

[@AshmitKumar-ip9tr]

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

[@pincetoons]

great job

[@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

[@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?

[@A2_26_Tushar_kalaskar]

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

[@vanshgawra]

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

[@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.

[@rahultiwary4257]

Happy Teacher ''s day

[@bite091_jamee7]

sir u r great

[@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.

[@darshitsheer2633]

When Mathematics and Algorithms combines. It ruins maths as we have to take approx in Algorithms Complexity.

[@sahilingale8906]

Thank You SO Much Sir

[@youngboys7342]

Thank you sir

[@JanakkumarPanchal]

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

[@vanditasharma368]

if possible teach us DIP AND CLOUD

[@gangadharamdantu9614]

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

[@devenpatel4684]

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

[@kaymylon9711]

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

[@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

[@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✌🏻

[@shahinparween3496]

Happy teacher day 🙏🙏

[@sayandatta389]

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

[@anurag3150]

I agree

[@Banditxam4]

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

[@dibyenduprodhan9089]

Happy Teacher's 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?

[@atifhassan8098]

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

[@RASmi-s_CREATION]

at 6:25 k=n-1

[@akatachadar2846]

Sir plz add videos for k map also in digital

[@adityatiwari9535]

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

[@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..💁🏻‍♀️

[@komal_0507]

bhaiya esme n-k=1 jo h toh vo k=n kese hua

[@sarthakjain1824]

Nice

[@SurajKumar-kn1ko]

Happy Teacher's Day

[@IAMLEO-hb4zb]

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

[@huzaifanoor]

After watching this veido ham apna hatyar otha ka sawal ko haal kraga 😂😂

[@Bhojpuriyabayar456]

6:20 pe sir n-k= 1 hai to k=n kaise ho jayega please sir tell us

[@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

[@Obnoxious_25]

This is easy 😎

[@sambhavgupta1203]

happy teachers day

[@SUPERMAN-zu6rr]

HAPPY TEACHERS DAY 🥺❤️