Solved Recurrence - Iterative Substitution (Plug-and-chug) Method
Vložit
- čas přidán 13. 10. 2016
- 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.
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
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.
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!
Much more straightforward than my professor makes it out to be.
You're a savior, This is so clear and concise, wish my professor had explained it like this. Thank you!
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!
How I was struggling with this concept but you made it so simple. I Salute you Sire.
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.
This is probably the BEST recurrence relation video I've seen, thank you so much!
Thanks, and you're welcome.
I'm so glad I found your videos before my quiz tomorrow. Thank you !
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.
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
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 teach better than the Algo teacher at ETH. Great job!
Best explanation on CZcams, you just saved my day, Sir.
Glad to hear that!
You are amazing ! I was stuck more than 3 days ! now got it . 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
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!
Great explanation and algorithm to go about solving these pesky recurrence relations! Many thanks.
Very clear. Good job John!
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.
This so much better our teacher makes us guess big o then from there we work through to find the asymptomatic notation
First comment of my 10 years on youtube. Thank god for your existence.
Best video. Super clear explanation! Great job
Thankyou man. Best explanation till now i've seen.
Dude, you are awesome. Thank you so much for how you explain each step.
So simply, fluid and clear. John Bowers for president!
thanks a lot brother for this amazing 9 minutes tutorial
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.
Very well done. Thank you John!
7 years later... thank you!!!
Best 9 mins of Substituting
Omg the first explanation ive understood thank you so much!
perfect explanation, clear to understand
very well done. This is what youtube is all about for me.
Extraordinary....Thank u Sir..Love from India
#WeIndiaWeWin
BEST VIDEO HANDS DOWN. Subbed!
That was elegant and very clear. Thanks
This helped me big time for preparing the mid term. Thanks!
same , I have my midterm next week
Excellent.. it's the best one in recursion videos
Very good practical example compared to the bad slideshow video lecture version offered at my university.
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 was helpful please upload more examples to solved recurance...
this video is a gem!
Thank you very much, you are great at explaining
you, my friend, are a SAINT thank you
Great work man, keep it up. THanks a ton!!
This video was very helpful. Thank you
The most intuitive way I think this one is.
Thank you for this video , it helped me to solve recurrence relations
yep, this is the best vid on repeated sub hands down
Thanks!
best example so far!
Thanks for sharing your knowledge, I got it.🎉
thank you , you saved my life
good explanation. made this method very clear.thankyou
Which method is best iterative or guessing and induction method??
Great video! Saved me on my final!
Hi, how do you get O(n log n) in the last step
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?
Why do the 2s cancel out at 3:46 ??
Seriously helpful - thank you so much!
Glad it was helpful!
Thank you, helped me a lot!
you just saved my life, thank you
It's been 7 years and it still the best video on the CZcams. Thanks for help!
I don't understand why its not n^2logn ,as we have 4n+4nlogn.Can someone explain?
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?
Can anyone please explain me why he multiplied both sides by 2^i?
Thanks a lot ! Very simple and useful !!
We do this as Iteration method. If question is asked to do by substitution method, can we do it? Whats the similarity?
great explanation ! thanks a lot
Awesome Bestest Video on Sbstitution Method
what if i have a case distinction between even uneven
when a = b it will be easy but what if a > b
how i can solve this ?
thanks for this super helpful video! my professor was nowhere close to being this thorough!
this was very helpful, thanks
beautifully done
I don't understand the last step that how directly you write the time complexity
Where did the T(1)=4 come from?
You are the real MVP
How did you know what to substitute?
How would this work if their is no base case
crystal clear! thank you!
This video is a gem. This is how to teach!
Thanks, glad it helped.
Insane video🙏🏻
you are the best. thank you very much for the amazing video
Sir can you upload a course algorithm analysis from scratch?
Thank you..It is helpful...keep uploading
Great walk through thank you
Really I understand very well