Solved Recurrence - Iterative Substitution (Plug-and-chug) Method
Вставка
- Опубліковано 5 жов 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.
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.
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.
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.
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!
This is probably the BEST recurrence relation video I've seen, thank you so much!
Thanks, and you're welcome.
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.
What my teacher could not explain in 8 hours, you did under 10 min. Thank you so much
Best explanation on UA-cam, you just saved my day, Sir.
Glad to hear that!
Much more straightforward than my professor makes it out to be.
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.
The best video I've ever seen about solving recurrences. Thank you.
You saved my CGPA, John. Thanks a bunch!
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.
I have watched many videos about this topic but your explanation is outstanding
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.
You teach better than the Algo teacher at ETH. Great job!
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 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.
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!!
You're a savior, This is so clear and concise, wish my professor had explained it like this. Thank you!
You are amazing ! I was stuck more than 3 days ! now got it . thank you
First comment of my 10 years on youtube. Thank god for your existence.
This so much better our teacher makes us guess big o then from there we work through to find the asymptomatic notation
It's been 7 years and it still the best video on the UA-cam. Thanks for help!
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.
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!
So simply, fluid and clear. John Bowers for president!
7 years later... thank you!!!
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
I'm so glad I found your videos before my quiz tomorrow. Thank you !
Thanks to you I have learned what I need to learn, finally.
Dude, you are awesome. Thank you so much for how you explain each step.
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
thanks for this super helpful video! my professor was nowhere close to being this thorough!
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!
Very clear. Good job John!
thanks a lot brother for this amazing 9 minutes tutorial
Extraordinary....Thank u Sir..Love from India
#WeIndiaWeWin
Thank you very much, you are great at explaining
you just saved my life, thank you
Very good practical example compared to the bad slideshow video lecture version offered at my university.
very well done. This is what youtube is all about for me.
Best video. Super clear explanation! Great job
Seriously helpful - thank you so much!
Glad it was helpful!
Omg the first explanation ive understood thank you so much!
The most intuitive way I think this one is.
Thankyou man. Best explanation till now i've seen.
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!
thank you , you saved my life
you, my friend, are a SAINT thank you
yep, this is the best vid on repeated sub hands down
Thanks!
That was elegant and very clear. Thanks
This video is a gem. This is how to teach!
Thanks, glad it helped.
Best 9 mins of Substituting
This was helpful please upload more examples to solved recurance...
this video is a gem!
Very well done. Thank you John!
best example so far!
One thing i learned today.. always do research if you dont understand something in paid lectures
Thank you for this video , it helped me to solve recurrence relations
Excellent.. it's the best one in recursion videos
Thank you so much, can you please collect the videos of algorithm under one playlist 🙏🏻
You are the real MVP
This video was very helpful. Thank you
I think you should make more videos over this topic sir and thank you
good explanation. made this method very clear.thankyou
Thank you so much for explaining it step-by-step! I was so lost in class today with the substitution method; But this video has made it more clear! Where do you get T(1) = 4 ? Do we make these up ?
You do not make up the base case, it should be given as part of the problem. If the problem was T(1) = 7, for instance, the final evaluation would be different.
Hey, John! You are amazing 🔥 I wonder why you stopped making videos....
its iterative method not substitution
Yes, the full name is the "iterative substitution method", which some people call shortly the iterative method whereas others call it the substitution method. This is a bit confusing, because there is also a guess-and-prove method that is sometimes called the "substitution method" as well. It depends on where you learned it what you call it. This is a common problem in mathematics. We've way overloaded a lot of mathematical terms (ever search for Cauchy's Theorem? I know of at least 3 different theorems in different areas of mathematics called Cauchy's Theorem in that field).
umm i see so we do iterative method anf find tiome complexity then use it for substitution method..bro i needed that 2nd part 1
No, this analysis above let's you get the closed form exactly. No need for a proof afterwards. What you are referring to as the "substitution method" is the guess and check, where you guess the form of solution, like T(n) is O(n log n), and then you prove, generally by induction that T(n)
tq bro..very helpful video and you are very helpful interactive teacher giving sugestion for comentators
crystal clear! thank you!
Thanks for sharing your knowledge, I got it.🎉
You're awesome!
Wow. I don't know how you got O(nlogn) but I'm I'm ready for my test tomorrow.
beautifully done
Awesome Bestest Video on Sbstitution Method
Ummmmm..
Can we have 1 or 2 more examples specially with log
If you don't mind. thank you
And you explained it superbly
You are the best, ever
The video is Great. Just give a little introduction in the beginning.
Thank you so much
great explanation ! thanks a lot
thank you a lot i was so confused when learning from textbook but now okkkkk
Thank you, helped me a lot!
Great video! Saved me on my final!
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.
Great walk through thank you
Thanks a lot ! Very simple and useful !!
this was very helpful, thanks
Great work man, keep it up. THanks a ton!!
hey, great video, though I would appreciate it if you could another one showing how to solve more complex recursive functions, such as one involving log(n) and without a base case please. would be forever grateful :)
Thank you very for making it so easy for me.
you are the best. thank you very much for the amazing video
Thank you
thanks a lot brother
Insane video🙏🏻