Substitution method | Solving Recurrences | Data Structure & Algorithm | Appliedroots
ฝัง
- เผยแพร่เมื่อ 7 พ.ค. 2019
- Chapter Name: Solving Recurrences
Please visit: gate.appliedroots.com/
For any queries you can either drop a mail to Gatecse@appliedroots.com or call us at +91 844-844-0102
I have been out of school for 10 years. I re-read CLRS and multiple other difference sources about this substitution method. I just forgot too much about induction that I could not follow those other explanations. This video really did a great job of explaining this very convincingly and clearly without assuming any knowledge of the audience. Great job, kudos and I appreciate your work so much!
Bro, thanks a lot. I've been trying to understand this shit for all day long and you just made me figure it out.
Man I wish I had seen this prior to my algorithms midterm exam. The prof just uses the examples from the textbook, but the way you explain the steps make it so much clearer to understand. I will definitely be using you as a resource from now on
that's what I exactly wanted from TH-cam. Thanks a lot
I watched five or so videos on the subject and this was the clearest by far. Thank you!
Is the assumption "all" m= n0? Hence might there exist m < n0 where the condition does not hold? Perhaps "some" m
Easy understandable and extensive.
Thanks!
Explained beautifully
Wow thank you so much , your a life savior 😢
For someone having hard time to guess the solution in one go,I recommend you to go through master's method first before stepping into this one.
Btw great lesson!
Thank you so much. This was super helpful.
Thanks for this video, I learned about inductive proofs just a while ago, where it was about proving that P(k+1) holds using P(k) (P = proposition)
So the explanation of using T(n/2) to show that T(n) holds was helpful. (Well, not T(n) but whatever was used with T(n), in this case, the inequality)
*Correct me if I interpreted something incorrectly here
Have you perhaps also made a video about repeated backward substitution? I learned about it in a lecture but the CLRS didn't cover it. If not, can you make a recommendation, where it will be explained as well as you did here?
Great explanation! It would be better if you also showed the base case proof.
One of best video on substitution method.
Thank you ❤
Amazing presentation u got a sub.
for 13:30 is it not possible to change it into cn -(-n) so the (-n) can be excluded hence it will prove that T(n)
Thank you for the explanation!
Awesome teaching.
Very well explained, thanks.
Special thanks for showing an example by taking a wrong guess value and explaining the pitfalls.
love u mate, that saved me
Does anyone knows what happened in this example?
Give the recurrence relation.
T(n) = 2T(n/2) + 1
Guess : T(n) = O(n) ===>>> T(n)
Not sure if I entirely follow your question but basically cn is another way of giving bounds for O(n). For all intents and purposes cn=O(n) but we ignore the c because we are only looking for an upper bound when using BigO notation so we just ignore the constant. It is also worth noting that with the master method there are a few fringe cases in which cases where it does not work. Namely when the leaves (divide step) are almost equal but not equal to the root (conquer step) because both case 1 and case 3 require them to be polynomially smaller and larger respectively. Case 2 of the master method can generally absorb a difference of about log n but if it doesn't fit in that log n difference and it doesn't fit in case 1 or 3 as shown before it can't be used. Hoped this helped and I'm sorry if I confused you more!
Youre using T(n) = 2T(n/2) + 1 vs the video using T(n) = 2T(n/2) + n which is completely different
Thank youn a lot!!, I was searching for something like this since 2 days
Pro tip: watch movies on flixzone. Me and my gf have been using them for watching a lot of movies recently.
@Alan Jesse Yup, been using Flixzone for since december myself =)
Who is Youn
Big O is n
Great explanation ♥️
seriously mate thank you! you deserve more than my lecturers!!!
how to guess the time complexity ?
@@priyankand3692 same doubt, do you now have the explanation for that?
On the mistake example .if there is minus n was it going to be true
My major problem has always been how to make the guess in the first place.
Anyway thanks for this video.
hello...i have exams in 2 days...did you get a better understanding on how to guess the answer or any other vdo you can link... please would it help a lot 🙏🙏
Thank you so much!
Can someone explain what m is? and why we choose it as n/2
Hi, in mathematical induction we typically have a base case. I was wondering how come we did not use it here?
For example, do we need to show that it holds for T(1) or T(2) etc...
Recurrence relations will usually have a recurrence T(n) specified for values greater than some n and a single value specified for T(1) or whatever the "base case" is (you might have seen the notation where you have T(n) = { "two lines for the two cases"). That T(1) would be the case where the recursion "bottoms out" and you would have for example just T(1) = 1. If you imagine a recursion tree, that is the cost of a single leaf at the bottom of the tree.
Thank you!
Thanks a lot!
superb explaination
thanks sir, it was a nice lecture
Note: without a base case you can't conclude anything using induction.
If we get any new recurrence how will we guess correctly.....there are other videos too on substitution where they substitute the values and find the series.... dats more easy I guess....here it's more sort of proving the answer rather than finding the answer
I don't understand how you went from cnlog(n)-cn+n to cnlog(n), can you elaborate on that step? time: 8:41
according to me he is saying that this whole term (cnlog(n)-cn+n ) is less then cnlogn because we are subtracting (c-1)n from nlogn. therefore we just use this relation to get t(n) = cnlogn -(c-1)n to t(n)
this probably isnt worth much to you after 6 months, but here's a simple example:
Take b as any number >= 0.
x = 2 - 1b
Therefore:
x = 0)
@@clashingwithsahib But this argument is not valid if c is something between 0 and 1. Instead, I think the reason he discarded the linear term is because asymptotically they are trivial compared to O(nlgn).
@@sarahli2933 Your reasoning seems more logical.
@@sarahli2933 actually, for the proof to be correct, he needs to state in the video that c is greater than or equal to 1, because according to the big O definition, we could pick any values for the c.
This helped a lot, thx. That being said, does it have to equal exactly? The reason cn + n is not cn because T(n) could be in between cn and n aka n(c+1). I have a similar problem where the f(n) in the recurrence is logn and you end up getting something like nlg^2(n) - nlgn + n (without the Cs) and the soln is O(nlg^2(n)), however it makes sense because while the nlgn grows faster, it's subtracting in this case and it's just obvious that nlg^2(n) grows faster than n. They do give a T(1) = 1. Are you supposed to use that somehow to finish the proof?
NVM I see.
the T(1)=1 makes things so much easier. i have to do some questions which don't even give that.
At 8:41 , you say that the expression is less than or equal because -(c-1)n is negative. Should we specify that the c should be greater than one for it to hold? or is it enough to realize that there exists a c greater than 1 such that the proof holds?
I think earlier he defined c as some constant greater than 0. Yeah, a 2:26
Sorry, I misunderstood your question. I don't know, but I guess you are right in that it is enough for there to exist one C greater than 1.
At 8:12, you said log2 is log 2 base 2 and changed it to 1. How did you know it was base 2? When I graph kx(logx - log2) and kx(logx - 1), I get two different graphs. How/why did you replace log2 with 1?
its not log, its lg. log is base 10, lg is base 2
Thank you good sir
thank you so much
how do you just guess correctly, there's so many options
you can guess any complexity and then check if it is true, he used the correct guess to teach us. if you use O(n^2) it will also be true, but it's loosely bound.
superb explanation sir
Thanks and welcome
Now I'm even more lost than I was before playing the video
thanks
in this example we have already know the T(n)=O(n logn) then we assume exist this .If does't know Then ?
you can guess any complexity and then check if it is true, he used the correct guess to teach us. if you use O(n^2) which will also be true, but it's loosely bound.
I liked how you get to the point and explain very simply!!!
you should have taught back substitution as guessing is tough
The proof is incomplete. The result we proved was for n/2 >= n_0, which is n>=2n_0. What we needed was to prove the guess for n>=n_0, so we still aren't done with the problem. We need to show that the guess is true for n_0
How he guess this ,if i guess O(n) in place of O(nlgn) then what happened?
Watch full video
you can guess any complexity and then check if it is true, he used the correct guess to teach us. if you use O(n) it will return as false.
like
very chaotic
very bad explained, in such a hard way, without a true example. I swear i will make a video of how to solve by this method when i learn it
i read this before watching so i assumed it would be a bad video but it actually explained well. i think you just don't have the prerequisite knowledge
@@emperor8716it is not bad, but he definitely jumps around a lot. Most people go fast with explanations because they expect fundamental understanding of core concepts(such as induction). This idea usually just leads to confusion since most people go to these videos because of their lack of understanding. A slower Way longer explanation void of expectations is far superior…
Thanks so much! This is really helpful.