L-2.5: Recurrence Relation [ T(n)= T(n-1) +logn] | Substitution Method | Algorithm
ฝัง
- เผยแพร่เมื่อ 3 ก.ย. 2021
- 👉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 TH-cam: / 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/gatesmashersofficial
► Follow us on Threads: www.threads.net/@gate.smashers
--------------------------------------------------------------------------------------------------------------------------------------
►For Any Query, Suggestion or notes contribution:
Email us at: gatesmashers2018@gmail.com
![L-2.6: Recurrence Relation [ T(n)= 8T(n/2) + n^2 ] | Master Theorem | Example#1 | Algorithm](http://i.ytimg.com/vi/FBKjvXGGCJM/mqdefault.jpg)
![L-2.6: Recurrence Relation [ T(n)= 8T(n/2) + n^2 ] | Master Theorem | Example#1 | Algorithm](/img/tr.png)
![L-2.4: Recurrence Relation [ T(n)= 2T(n/2) +n] | Substitution Method | Algorithm](http://i.ytimg.com/vi/VHGisohk3Ck/mqdefault.jpg)
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....
log 0 will come if we take k=n-1, which is impossible to solve...
final ans bata, kya hai to
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
@@himanshushah6746 wrong question * { 1 if n=0 }
Thanks bhai Mera sir phat gaya
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.
Answer will be same with same mistake 😳
Yess you are right
I too got stuck there thinking it'll be 2 😂
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
Yaa You Got It Bro 👍😉
At 7:20 of your video....sir
n-k=1
n-1=k aayega...not n=k
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))
T(0)=1 may be the Equation
you are right
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. 🙏
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.
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.
Happy teacher's day sir. Thank you so much to help us for gaining knowledge.
TIPS: Take the two conditions as n = 0; n >0; Rest will be fine.
Hope it helps you, guys.
Love you sir ❤
Bro, you are saviour 🫡
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.
dear sir here n-k=1 then k will be n-1 and whole equation and question will change at 6:30.
Happy teacher's day 👏👏👏👏 love from Gujarat
bhai ek hi dil h kitne bar jitoge......
lots of love from Bangladesh.....keep up the good stuff
thank you you made day .
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.
Thank You SO Much Sir
Happy teacher's day sir✨♥️
Thank you sir 😊
Pls tell how n-k=1 statment is becomes n=k
No,it is n - k = 0
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.
Yes it's k=n+1
@@ananya88agrawal answer mil Jai toh batana 🙂
@@ananya88agrawal k= n-1 😊
Thanks sir 😊
Happy teacher's day Sir... 🙏
Happy teachers day to varun sir 🙏
Happy Teacher's Day Sir 🙏❤😊
great job
Thanks sir
There is one mistake in given condition everyone should be corrct it....
if n=0
if n>0
This are the correct condition given...👍🏼👍🏼
sir u r great
Happy teacher's day sir
You are the best teacher for CSE students...you work so hard for us
Thank you so much ☺️
Thank you sir
Happy teacher's day sir 🙏
If agr last tak ka part smjh nhi aaye then what to do please tell
Happy Teacher's Day Sir.
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
Completed whole playlist today, thank you sir for your efforts, will donate a big amount soon.
Can you please share your notes?😊
@@cpwithtausif4866 I can share but I have done till lecture 17
@@cpwithtausif4866 But I was wondering how are you getting these lectures, these are a mix of both hindi and english ?
I will donate after I get placement 😂
@@anugrahmasih6347 whats there to wonder lol, if you understand both hindi and english, its simple
There's something wrong while solving the recurrence relation, when we have to eliminate T(n-k) to make it 1 you take the condition that n-k=1 so, it will become k=n-1 and if we substitute it in the equation it'll become T(1) and it'll be eliminated, you made n=k and it will make T(0) and how to satisfy this??
It was a mistake. k will be equal to n-1 and it will make T(1). The reason why sir took it as 1 because according to him, he made correct relation between k and n. So, he just wrote 1 without checking.
Happy Teacher's day sir ✨☺️
Sir agar kisi question t(1) =1 wale conditions nhi mention h to kya hum apne man se maan ke solve kr skte hain?
Happy Teacher's day Sir😍
Happy Teachers day sir❤️
Happy teacher's day sir
Happy teacher's Day sir
Computer science ka kuch pta hi nhi tha... Itna interest se pdhaya ki hr topic ka pta h ab apse pdhkr
I haven't started studying yet, so can you please tell me does this channel has the complete course for GATE?
Sir how n-k= 1 became K=n ? It must be n= 1+ k right?
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
sir how to solve recurrence relation by tree method? plz upload video on that
Happy Teacher's Day Sir :))
Happy teacher's day sir ji
tiem complexcity = 0(n^2 logn) , hai kya
is it correct
Happy teacher's day 💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐💐
🌸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✌🏻
Nice
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.
KING
yhn jo aapny n-k=1 lya hy so eq me wo bhi tw put krskty hy
Sir u are super duper awesome. I really appreciate your effort and your style of teaching .Really JazakAllah🤍
It is wrong why n=k
I do think the complexity will be log n as the series goes like t(1), log (2), log(3), ……….. log(n)
the number of log terms is not fixed, it will depend on n, that's why the complexity is not logn
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
how is n=k when n-1=k. k should be n-1 right?
6:20 pe sir n-k= 1 hai to k=n kaise ho jayega please sir tell us
Happy teacher day 🙏🙏
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
how it is possible if n-k =1
then k=n
how it is possible sir??
n-k=1 then k=n-1?
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)
if we taking log as a common then in bracket it should be 2+3+4+5+6.. isn't it
This is easy 😎
Happy teacher's day to our best teacher.may god bless u with all the happiness and peace in life 💐💐
Sir please make video on class p and Np completeness .. please sir i am watching your video from my college starting period of time.
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
Which formula ?
@@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...
Pls isko sahe tara se explain kre not understanding
Can anyone say that how I purchase gate smasher's paid course?
Is this playlist completed
If n-k =1
So n =k-1 nai?
I did it by using n-1 steps instead of k steps and i also got the same answer
n-k=1
So that K=n-1
How can possible sir n=k
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)
yeah
we put n-k=1 *** -k=-n+1 *** k=n-1. we have to substitute k=n-1 not n.
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.
sir, i guess n-k = 1 will give k=n-1....
can we take this steps n-1 instead of k?
Did you got the answer?
HAPPY TEACHERS DAY 🥺❤️
(k) ki value galt nikali hai kya?
Sir plz add videos for k map also in digital
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..💁🏻♀️
Question is wrong..... if n=0 & n>0 then n-k=0 => k=n
Smasher bhaiya zindabad gate fod denge .......is baar lgta hai .
i have taken n-k =1 and got the same answer .😊
Haa in last 1 + n log n - log n and then
n log n dominating so order will O(nlogn)
happy teachers day
Sir 6:25 ke baad ghanta nhi kuch samajh aaya...
T(n-n) = T(1) kaise hua???
n-k=1 => n=k kaise hua???
Happy teacher day Sir! and at 6:25 n=k is wrong as you said n-k=1
Sir in this at 7:50 if n-k=1 then k=n-1 ?
Right or wrong
Sorry At 2:25
@@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
6:25 n-k= 1
Can someone say that this recurrence expression is for which problem (matrix multiplication, knapsack , maximum sub-array, etc)?
if possible teach us DIP AND CLOUD
n-k=1 ,then k=n-1 but you write k= n
Me b yehe pooch rahe how it becomes ?
the same confusion is also here.
@@hafeezaslecturesofcomputer4427 that was just typo....use your common sense....
By mistake n-k=0 it is
completed
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
If agr last tak ka part smjh nhi aaye then what to do please tell
bhaiya esme n-k=1 jo h toh vo k=n kese hua
Bro k=n kese Aya , n=k+1 ayega na??
Happy Teacher's Day ❤
how n = k ?? i don't understand anyone can clarify??
Happy Teacher ''s day
sir n=k how sir n-k=1