Solved Recurrence - Iterative Substitution (Plug-and-chug) Method
ฝัง
- เผยแพร่เมื่อ 19 พ.ย. 2024
- This is an example of the Iterative Substitution Method for solving recurrences. Also known sometimes as backward substitution method or the iterative method.
An example of solving the same recurrence using the Tree method can be found here: • Solved Recurrence Tree...
Note that there is another method of solving recurrences that is unfortunately called the substitution method by the CLRS Algorithms Book that many R1 instructors use to teach algorithms. This other method is not a little bit like the iterative substitution method used here. It is more accurately called the "guess-and-check" method, since you make a guess about what the runtime is and then prove it by induction.
In a quick survey of the Algorithms textbooks near at hand, CLRS and Klienberg & Tardos call the "guess-and-check" method "substitution" while the books by Neapolitan and by Levin, call what I did the substitution method. Leafing through Rosen it appears to only show the substitution method, but it doesn't name it. Epp's book calls this method the iterated method and does not teach the other method.
The bottom line is that in mathematics it is often the case that a single name is used to refer to multiple things and sometimes a single thing may have multiple names. Even in the same subfield. It's important to remember this and that it's not the name that matters.
You are the hero in the night. The dancing of the flowers in the wind. The moonlight dipping into the sand. Thank you John. On all my next exams, I will write “This one’s for John.” before all recurrence relations.
Learned more in 10 minutes, than in the 2 lectures covering this, thanks.
They did 2 lectures to cover just this ??
Exactly 😂
Literally same here, only had 2 lectures
True LOL. Glad I found this treasure.
I came here to say exactly this. Two full lectures covering this and I still was confused, and this one video and I finally get it.
It's been 6 years and this still remains one of the best videos on this topic.
I learned something in 9 minutes that I couldn't learn in 3 hours while in class. Thank god people like you exist!
In case you were wondering, this is still super helpful to people (at least, me!) 7 years later. Thanks.
This was really helpful. For some reason the most intuitive substitution method video I've seen. Thanks a ton.
Thanks! Glad you got something out of it.
Out of all the videos I have watched trying to help me solve recurrences, yours has been the most helpful one and has finally helped me figure out what everything means. Thank you for explaining every step and where you got everything. Thank you so so much.
What my teacher could not explain in 8 hours, you did under 10 min. Thank you so much
This is probably the BEST recurrence relation video I've seen, thank you so much!
Thanks, and you're welcome.
I know you uploaded this seven years ago but from all the different videos on explaining this method, you're the one that did it in a clear way that I can actually understand. Thank you.
I was absent my algo class of recursive algorithm / solving recurrence, and your video helped me from suffering the pain of solving recurrence problems, perfectly. Thank you for you detailed explanation and step to step tutorial.
Much more straightforward than my professor makes it out to be.
The best video I've ever seen about solving recurrences. Thank you.
First comment of my 10 years on youtube. Thank god for your existence.
Best explanation on TH-cam, you just saved my day, Sir.
Glad to hear that!
You saved my CGPA, John. Thanks a bunch!
You teach better than the Algo teacher at ETH. Great job!
This has got to be one of the best explanations. The only step that's missing which is beyond the scope of this video is the induction proof at the end to show that T(n) = O(n log n) for all n>1.
I have watched many videos about this topic but your explanation is outstanding
Can I just have you as my algorithms professor?
Yes, you can! Come to James Madison University =D, we've got lots of great CS Profs!
It's been 7 years and it still the best video on the TH-cam. Thanks for help!
You're a savior, This is so clear and concise, wish my professor had explained it like this. Thank you!
I was looking for this solution for hours in the other sites. You have the best (and the most detailed) style of explanation. I really don't know how can I thank you. Shared with friends. And THANKS A LOT!!
It is really helpful
Thanks john
I have exam day after tomorrow but I even don't know the methods of solving recurrence it is really helpful ,simple to understand and remember
This so much better our teacher makes us guess big o then from there we work through to find the asymptomatic notation
So simply, fluid and clear. John Bowers for president!
This video was great and was the one that helped it all finally click for me. It was essential that this example had an n outside of the T(n/2) so I could see how that was handled. Now I'm struggling to solve a recurrence that is divided into different sized sub-problems (ie: T(n)=T(n/2)+T(n/4)+T(n/8)+n, where T(1)=1) using substitution and am wishing I had another video of yours as reference.
You are amazing ! I was stuck more than 3 days ! now got it . thank you
With this video, solving recurrence by substitution is tick. Thanks for the video although its like more that 5 years since the upload, it is still helpful.
ohh my gawddd this video ........i was searching for a video that broke this process down and finally i got it thank you good sir
7 years later... thank you!!!
The most intuitive way I think this one is.
Very well done. Going through the 3rd step was a good call as well. Basically, the other videos on this topic are a bit too theoretical or obscure. This iterative way of performing the method is much easier to follow. Thank you!
very well done. This is what youtube is all about for me.
I'm so glad I found your videos before my quiz tomorrow. Thank you !
I'll be honest, I was NOT expecting the O(n log n) bomb at the end.
Just use limits to verify. Limit as n goes to infinity for (4n+4nlog_2 n) / (n log_2 n) , which = 4 , which means it is O(n log_2 n indeed)
@@Amy-tw3zh Hi, can you further clarify how you can relate 4 to O(n*log_2(n))? I understood everything up until 4n+4n*log_2(n).
@@Twannnn01 You need to compare all the joints of the expression asymptotically. It's a little hard to explain, if you don't know what it means already. But basically, it means what @Mandey just said: To compare the values, when n is infinitely high. Take a look at the graph on this page to see if you can get the picture: www.bigocheatsheet.com/
That O(n log n) thing is sneaky. Can't turn your back for a second or it'll get you.
Thanks to you I have learned what I need to learn, finally.
yep, this is the best vid on repeated sub hands down
Thanks!
thanks for this super helpful video! my professor was nowhere close to being this thorough!
thanks a lot brother for this amazing 9 minutes tutorial
This video is a gem. This is how to teach!
Thanks, glad it helped.
Thank you for the helpful video! I appreciate the step by step process especially since math isn't the strongest subject I have. Thank you sir!
Extraordinary....Thank u Sir..Love from India
#WeIndiaWeWin
Best 9 mins of Substituting
Very good practical example compared to the bad slideshow video lecture version offered at my university.
Great explanation and algorithm to go about solving these pesky recurrence relations! Many thanks.
perfect explanation, clear to understand
This helped me big time for preparing the mid term. Thanks!
same , I have my midterm next week
Dude, you are awesome. Thank you so much for how you explain each step.
Thankyou man. Best explanation till now i've seen.
Very clear. Good job John!
you just saved my life, thank you
best example so far!
you, my friend, are a SAINT thank you
Best video. Super clear explanation! Great job
Thank you very much, you are great at explaining
That was elegant and very clear. Thanks
Omg the first explanation ive understood thank you so much!
Seriously helpful - thank you so much!
Glad it was helpful!
My question becomes now: do we need to inductively prove for this? most books have an induction proof for solution, but they follow a "guess the big-O" before starting to do the math!
this video is a gem!
Excellent.. it's the best one in recursion videos
You are the real MVP
Very well done. Thank you John!
Thank you for this video , it helped me to solve recurrence relations
You're awesome!
thank you , you saved my life
This was helpful please upload more examples to solved recurance...
good explanation. made this method very clear.thankyou
You should be the author of textbook
push the subscription button right away after finishing the video...! The number of subscribers do not justify his content....
This video was very helpful. Thank you
I think you should make more videos over this topic sir and thank you
Awesome Bestest Video on Sbstitution Method
stupid question: howd you come up with the base case?
It's given to us with the recurrence relation. Say you have an algorithm, you can always check how many operations are performed for an input size of 1, i.e. the base case here.
You are the best, ever
YOU are THE G.O.A.T
Thanks for sharing your knowledge, I got it.🎉
Thank you so much, can you please collect the videos of algorithm under one playlist 🙏🏻
Great video! Saved me on my final!
First i solved a question .... Thank you so much
The video is Great. Just give a little introduction in the beginning.
beautifully done
crystal clear! thank you!
thank you a lot i was so confused when learning from textbook but now okkkkk
At 3:40 when the 2's cancel, I don't understand why its still 2^2 if we used one of the twos to cancel out denominator and get 4n. I am confused. Can someone explain?
Hey, John! You are amazing 🔥 I wonder why you stopped making videos....
Thank you so much
wow explanation is GOOD AF
Great work man, keep it up. THanks a ton!!
Thank you very for making it so easy for me.
Do you know how we would approach Fibonacci recurrences? As in, an equation of the form
T(n) = T(n-1) - T(n-2) using the same method?
When performing the recursive substitution (as the first step) would you plug (n-1) into into the T(n) then take that value (here you calculated it on the "expand scatch" side) and plug it back into the equation (on the "build solution" side) for T(n-1) leaving the T(n-2) as part of the 'new' equation.
Or do we plug both (n-1) then (n-2), from T(n-1) and T(n-2) into T(n), as the first step, and expand on both?
Great walk through thank you
great explanation ! thanks a lot
This is easy after all!!
Thanks a lot ! Very simple and useful !!
this was very helpful, thanks
you are the best. thank you very much for the amazing video
thnx . this is the best video for recurrence
Thank you, helped me a lot!