L-2.8: Recurrence Relation T(n)=T(√n)+logn | Master Theorem
ฝัง
- เผยแพร่เมื่อ 24 เม.ย. 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.9: Recurrence Relation [T(n)= 2T(n/2) +cn] | Recursive Tree method | Algorithm](http://i.ytimg.com/vi/bJg_sv7PV-g/mqdefault.jpg)
![L-2.9: Recurrence Relation [T(n)= 2T(n/2) +cn] | Recursive Tree method | Algorithm](/img/tr.png)
![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)
![[UNCUT] ที่นี่ที่แรก ปู - หาญส์ พูดถึงมหากาพย์หนี้สิ้น I คนดังนั่งเคลียร์ I 10 ก.ค.67](http://i.ytimg.com/vi/KDNA9DZ0p4U/mqdefault.jpg)
Explanation of this type of case is not done in master method previous classes please explain.
Yes you are right but u can apply same trick or concept that he explained in previous video u can get the same answer
exactly, it was explained to be done in a different way. i got really confused.
@@saumyadeepkundu828same yr
Exactly.
aur uske upar yeh bar bar bole ja raha he age explains kar rakha he mene Sare vdos dekhliya aur methods alaga he aur v jada confused to isme he ho geya 😢
@@iamsm2001 So can you tell me konsi vid dekhni chahiye, ek Abdul Bari ki bhi hai vo sahi hai?
though i'm a medical student i subscribed to this channel coz my brother asked me to do it cz u deserve it......
Oh bhai kisine abhi tak hi bolke contact nhi banaya , nice comment section 😂
ohh shut up...
I am medical student
Thank you so much sir 🙏🙏🙏...Was waiting for long to solve this question...And u smashed it😎
at 5:00 , what if the condition is a>b^k?
Sir I solved this without any substitution.
n>=2 so n^½ >1 for sure. So I replaced n½ with n/n½, and got the same answer. With fewer steps too.
Sir if the case i.e h(n) is in the form of
log(n)/n^(i) or n^(i)log(n)/n^(j) (here i,j € Z+) ....
Then what will be the value of u(n)?
Dude confuse kar diya isse phele master method Vali video mai p tho pure board par nhi tha. Sikhate alag method ho example bhi ussi method loge par question alag method se solve karoge. Yaha chl kya rha hai bro?
😂
Jisse bhi doubt hai ki alag concept hai, please ek baar usi method se karo jo sir ne isse pichli wali video bataya tha. Mera sahi answer aa gaya us approach se
Nhi aa rha usse 3rd wla condition apply ho jaa rha
@@shantanubanerjee2842same problem
In the previous 2 videos of DAA playlist same method is there but this video is little bit different and general formula is also different .Anyway video is very nice
Exactly!
yeah, the formula is different compared to previous video 🫣
Yes Bro
the ans is same for both the previous method and this method
Thank You so much Varun Sir. You are a star and you owe a high place in our hearts--Your Unknown Student..BTW I am a 2011 passout (b.tech). Have 2 yrs exp in IT and 4 years experience in PNB as a Manager. Left my job to come back into my field..Kash aap hume pehle mile hote..!!
Thank you for the appreciation..
@@GateSmashers hello sir, non hindi speaking aspirants are also followers of this good platform.why don't you consider us too? Request for english subtitles atleast..
@@Girija_Mohanraj not hindi Speakers can learn hindi
If you can learn English, even if it's the non native language, then surely learning Hindi is not a big task, already it's a very simple language, and will come handy
Why to be language handicapped
I know my native language, marathi, hindi and english
Now it's different that you have some cultural enmity with hindi
@@thealphaprime4270 ha bhai,yeh south wale hmesha,har jagah aise hi spam krte hai.
Hindi ko pdna,yeh gulami smjte hai
@@mgryzen3679 gulambi 🤣🙌
Sir aapne k aur p last video m bataya hi nhi :(
exactly
My friends tell me about you channel , you are the " BEST " ....
sir, can we solve this by another way you have mentioned in other videos of master method??
For those asking how did we take T(2^m) = S(m) and used it to get T(2^(m/2)) = S(m/2) , well we just replaced 'm' by 'm/2' thats it. We did NOT take 1/2 as a power of m, we simply let our 'new m' equal 'm/2'.
Is this correct math's here
@@mdsaqlain3099 i dont think so this is correct
@@CSE___SHIVAMCHHABRA That's correc you can think either way, that's mathematically correct , she just substituted the m with m/2 .
Why has a different formula been used here for master theorem ? Can we not use the one used in previous video ?
I have a doubt why sire used the from T(n) = aT(n/b) + n^klogn^p is it an eception to use it or we made general form from the equation.
hey! can u plz give an example whose recurrence relation is this? I'm not able to find any ,plz if u could help!
Explanation of this type of case is not done in master method previous classes please explain
Thanks a lot sir....your videos have proved to be a real aid ❤️
Great teaching methods
Question-I:
Assume that we modify the binary search algorithm and instead of one middle point, we take two
middle points at each stage.
1. What will be recurrence relation of such a modified algorithm?
2. Prove that this algorithm will work
Ttly.
Question-2:
Write down the recurrence relation of Sequential Search algorithm if implemented recurs•veiv
Question-3:
What is the loop invariant of merge operation in merge sort algorithm? Why merge a:gonthm
better than insertion sort algorithm? Justify your answer.
did u get the answer yet?
Too long
Thank you sir teacher method is good 😊
Sir at 1:07 aapne f(n) ki jagah n^klog^pn kyu likha pls explain?
I have also same question
mujhe bhi nahi samjha
same question
@@krsnabantai woh extended Master theorem use kiya hai
sir ye playlist complete kb hogi?
so nice tutorials helps me always....i have a doubt that How many types of Recurrence Relations is there
two types 1. Linear RR 2. Divide n conquer
Very good work
In this solution, you have put T(2^m)=S(m). This also shown to have effect T(2^m/2)=S(m/2)
I am not able to understand how is happening.
T^(n)=T(2^(m/2)+m)
Now we assumed T(n)=T(2^m)=S(m)
and then Substituted the above equation by writing S(m) instead of T(n).
I also didn't get this.
same concern
@@Anonymous-sf1by bro if you have let T(2^m)=S(m) and your are saying that T(2^m/2) will be S(m/2), then what will be substitution of a function like T((2^m)/2) it will be also S(m/2). but functions T(2^m/2) and T((2^m)/2) are not same yet according to your method it is giving same result how?
from where had u studied daa for ur exams plz tell
Sir y jo aapne samjhaya h esse pehle kab bataya h bta sakte h aap kya
4:53 ye case wali video konsi ha?? Pichli videos mai to ni hain
can this be solved by substitution method ?
where is the video about a
sir apne iss vide mein, master theorm ke new concepts use kiye hai. Joh apne pichle videos mein cover nahi kiye hai
bhai playlist ki kuch kuch video me blue hai kuch kuch me yellow hai aisa kyun?? ek hi rakhna chahiye na
Thnk u sir for this. This was needed🤗🤗
Ur lectures are really helpful 👌
Great ❤️🔥🎉🙏
Doesn't getting, log 2 with default value of base 2 how?
how will you solve t(n) = t(n/2) +nlogn by this rule . I don't think we can find it ?
Instead of using *T(n)= aT(/b) + n^k log^b n* i used the formula that u explained in ur previous video i.e *T(n) = n^log^a b [U (n)]* nd got the same answer.. Could u please weather it's correct or not.?
Same doubt is it correct ?
++
@@adarshkumar2477 what
@@learncseasily3385 same doubt
but plz tell how u applied that formula .cuz to use that formula b should be greater than 1 and here b=1.
For those unable to understand
T(n) = aT(n/b) + n^k(log^p(n)) // Mater problem format
if a > bk, then T(n) = θ(nlogba)
if a = bk, then
(a) if p > -1, then T(n) = θ(nlogba logp+1n)
(b) if p = -1, then T(n) = θ(nlogba loglogn)
(c) if p < -1, then T(n) = θ(nlogba)
if a < bk, then
(a) if p >= 0, then T(n) = θ(nk logpn)
(b) if p < 0, then T(n) = θ(nk)
bro, sir hasn't teach this from where i can learn this ?
Hey can you tell me this question please
Solve the recurrence relation using master theorem T(n) = T(n^½) + C
isse pahle wale video mein kuch or bataye the master theorem or abhi kuch or . pls explain
Y formula changed from previous videos
Sir this is not a negetive comment but you haven't told about k in master theorem section
sir yeh achanak se method change krdia master theorem ka? aise thori hota hai? pichla abi smj aya tha ke apne naya aik method nikal diya, boss bht mishkil horhi hai yahan pe
i think he forgot to upload this method explaination video
@@itzmranonymous han shyd,
00:06 The video discusses solving Recurrence Relation using Master Method and Back Substitution Method.
01:10 Convert the given formula to a special format
01:58 The value of 2 power m remains unchanged in the equation
02:43 Convert 2 power m to function of S m
03:37 Understanding Master Theorem
04:18 The value of P is 0 in this case.
04:56 Master theorem helps in determining the output of a function based on its input size
05:41 The output of the recurrence relation is Log N.
Crafted by Merlin AI.
Those who are thinking that the method sir is using here is different and sir didn't teach in previous lecture. Bro, just use the previous method, you will get same result
Sir esss wale question m f(n) kha h u(n) kha h or h(n) kha h kuch samjh nahi aaya esa laga jesa aapne acche s nahi samjhaya
Sir in this value of p should be equal to 1 as at p=0 log become infinite
p is in the power of log, how can the log value become 0, it will be 1, coz anything power 0 is 1
TBH peechla saary examples clear ho rhy thymaster theorem ky until I stepped upon this one.xD
Sir please upload video on backtracking and branch and bound 🙏
explanation of this type of case in not done in master method previous classes please explain
Sir iss question me compare karke hum b ka value 1 nhi le skte kya 😅
sir the video on extended master theorem is missing in the playlist
Hey can you tell me this question please
Solve the recurrence relation using master theorem T(n) = T(n^½) + C
pls share the substitution solution for this
Please do a video on amortized analysis
Anurag bhai mast prediction
Super cool
why did we assume it 2^m??
itni baar bole hoki pehle bhi master's theorem padha rkha hai, aur waha kuch aur hi padha rkha hai aur idhar kuch naya leke baith gya hai....
can anyone explain why sir used 2^m as as assumption for substitution
Because it given in question that if n>=2
Sir...MCA through distance is good option or not...plzz answer😊
No. distance courses are risky nowadays.
Sir can you please share some topics of computer graphics also. I really need your help🙏🙏
Kb tk khtm ho jaiga ye course.... Please btao
Hello bro i need a help ?
Sir aapne master theorem me pichli bideo me k aur p se related juch bataya hi nahi hai aur yaha bata rahe ho co fused
Sir aap ka course chahiye pgt tgt computer science please inform me
sir notes is not accessible
Varun isse que ko substitution method se bhi solve krke dekha do plz
To those who are confused about the new formula, use the formula that sir has taught in previous videos and it also produces the same result.
mater theorem also have other cases which is not taught in this video and because of that i got less marks in my sem exams.
me too
Esse kase kuch bhi assume kr lete h....smj nhi aa rha hai
I'm so confuuse ☹️☹️
arey yeh vala method se yeh ques explanation toh apne kabhi btaya hi nhi
i think log(m) should be there instead of m.
Sir substition method se bhi solve kr do
This video makes me to believe that we can use master theorem in every kind of questions right ? By assuming
😂
Sir stay safe and healthy.and thank u
great explanation sir , but in the master theorem you put T(2^m)=S(m) and the eq T(m)=T(s^(m/2))+m become S(m)=S(m/2)+m , I don't think this step is correct .
Hey can you tell me this question please
Solve the recurrence relation using master theorem T(n) = T(n^½) + C
Bhai ye wala samjh nahi aaya yr to alag case hai explain karo acche se please
love you sir huge respect to you
Thank you
T(n)=T(cube root of n)+log n base 3
Answer plz
Sir dsssb k liye kuch test series or vedio laate plz sir
Well, I tried with the previous method of this series..and my ans came out🙌
Pichle concept se 3rd wla condition apply ho rha or ans log^2(n) aa rha
Hlo students m esliye y baat bta rha hu jisse ki koi students in future agar y video dekhe to pareshan na ho, sir n jo y question kraya h or jaise samjha rhe h wo bilkul thik h but but sir n y nahi samjhna h ki what is the k and p so, sir n jab master therorm padai h usme nahi samjhaya enn terms k baare m agar aapko samjhna h to abdul bari sir n full information dee h waha s seekh sakte ho. Okk mera koi esa intension nahi h ki m sir ki knowledge prr doubt krr rha hu esa nahi ho jaati sab h galti. Okk fine
Jai hind🙏👍
from where had u studied daa for ur exams plz tell
@@itzmranonymous hlo brdr abdul bari sir best video or bhi TH-cam prr acchi acchi video h jisse tumhe samjh m aaye usse krlo apna topic dekho video dekho and resolve your problem 👍
Sir,,,I completed b.com ,,,may I get IT company jobs by learning some programing language
bhai mai IT branch ka hui , hmko nhi mil rha, chup chap HR me ha
@@darshanpatil6692 from where had u studied daa for ur exams plz tell
Sir t(2^m)=s(m) hua to t(2^m/2)=s(m^1/2) jona chahiye , samjh nhi aya sir pls help
Same concern
hnn yr whi toh?
Koi hme btaiga ki ye playlist complete ho chuki hai ya abhi aani baaki h..... Please reply...
from where had u studied daa for ur exams plz tell
completed
Sir i am having problem in solving the same question by back substitution please explain
did u got the answer??
@@kalpeshvanage2528 I am also facing the same problem. Could you solve?
by substitution, answer will be O(logn)
sir pgt cs ka class karwaye.
bhai kya chl rha hai ye .... abhi tak to esa koi step bataya bhi nhi puri playlist line se dekh rha hun master theorem me saaari condition btaya hi nhi abhi tkk aur har baar hi bol rhw ho btaya thai padha diaya 🤨🤨🤨🤨
same bro, acahanq se kuch naya information de diya isne. wtf
sry sir yaha pay aap bht confuse kar rahi ho sb mix kar rahi ho aap please sir point by point explan karo na please sir
Excellent
Sir, please make some video about computer graphics. Lots of love and respect ❤️❤️❤️.
I simply did it with substitution method 😂
3:40 pr samjh ni aara S(m) = S(m/2) +m kaise aaya ?
same doubt bro?? @gate smashers
Thankyou infinite🥰🤩
You teach so well Varun, great work
Varunnnn, sir hi bol do yrr
@@aryan2228 sorry but there was no intention to disrespect him in any way, I really respect him and his teaching style, no worries I'll keep that in mind :) thanks
Sir its wrong the answer will be lognloglogn .
Sir your teaching......100000/100000
This topic is now going on in my university 😍
Hi