Solved Recurrence - Iterative Substitution (Plug-and-chug) Method

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.

[@Bonzo632]

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.

[@Shefetoful]

Learned more in 10 minutes, than in the 2 lectures covering this, thanks.

[@thetomatoes7075]

They did 2 lectures to cover just this ??

[@charulatha.p2782]

Exactly 😂

[@danielgilder8672]

Literally same here, only had 2 lectures

[@WarmHugSeeker]

True LOL. Glad I found this treasure.

[@allissahertz1769]

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.

[@alanbiju1765]

It's been 6 years and this still remains one of the best videos on this topic.

[@electricwatches1]

I learned something in 9 minutes that I couldn't learn in 3 hours while in class. Thank god people like you exist!

[@gerritgerritsen2113]

This was really helpful. For some reason the most intuitive substitution method video I've seen. Thanks a ton.

[@johnbowers5447]

Thanks! Glad you got something out of it.

[@bigboykazmi]

In case you were wondering, this is still super helpful to people (at least, me!) 7 years later. Thanks.

[@AiSeii]

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.

[@hydrophobicwalrus749]

Much more straightforward than my professor makes it out to be.

[@CaptainJellyBS]

Can I just have you as my algorithms professor?

[@johnbowers5447]

Yes, you can! Come to James Madison University =D, we've got lots of great CS Profs!

[@fuudonanma1411]

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.

[@luizlencioni6340]

The best video I've ever seen about solving recurrences. Thank you.

[@halfnorth]

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.

[@jesusalejandrorodriguezgar2735]

What my teacher could not explain in 8 hours, you did under 10 min. Thank you so much

[@ToasTeR1094]

You're a savior, This is so clear and concise, wish my professor had explained it like this. Thank you!

[@MorganAriel]

This is probably the BEST recurrence relation video I've seen, thank you so much!

[@johnbowers5447]

Thanks, and you're welcome.

[@sherazbutt6012]

I have watched many videos about this topic but your explanation is outstanding

[@GreeeenT]

I'm so glad I found your videos before my quiz tomorrow. Thank you !

[@mundapakistani]

How I was struggling with this concept but you made it so simple. I Salute you Sire.

[@bh_umbc]

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!

[@bh3302]

Dude, you are awesome. Thank you so much for how you explain each step.

[@kedarnadkarny4718]

Very clear. Good job John!

[@MrAbbasalrassam]

You are amazing ! I was stuck more than 3 days ! now got it . thank you

[@Jindujun]

Best explanation on TH-cam, you just saved my day, Sir.

[@johnbowers5447]

Glad to hear that!

[@TheChug00]

Best video. Super clear explanation! Great job

[@contrafoz]

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.

[@thetomatoes7075]

You teach better than the Algo teacher at ETH. Great job!

[@FarazKhan-xd4bd]

Thankyou man. Best explanation till now i've seen.

[@moisascholar]

Great explanation and algorithm to go about solving these pesky recurrence relations! Many thanks.

[@phillip3m]

Very well done. Thank you John!

[@redacted6673]

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

[@sirxavior1583]

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.

[@karamveeryadav8824]

thanks a lot brother for this amazing 9 minutes tutorial

[@ashwanivarshney9406]

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

[@MrGeorgerocker]

Omg the first explanation ive understood thank you so much!

[@hakancemgercek]

Thanks to you I have learned what I need to learn, finally.

[@dilaragoral2259]

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!!

[@gunaygultekin]

perfect explanation, clear to understand

[@davekaushik4863]

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!

[@chrisogonas]

That was elegant and very clear. Thanks

[@dinklemuffin8132]

This video was very helpful. Thank you

[@SuperRashadWilliams]

This so much better our teacher makes us guess big o then from there we work through to find the asymptomatic notation

[@tahamagdy4932]

Best 9 mins of Substituting

[@jakobhansen9688]

Thank you very much, you are great at explaining

[@darshilshah3941]

Great work man, keep it up. THanks a ton!!

[@geogaddi84]

very well done. This is what youtube is all about for me.

[@salmaabobakr1406]

Excellent.. it's the best one in recursion videos

[@luisbremer9351]

this video is a gem!

[@olivia0909]

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.

[@alvinkatojr]

So simply, fluid and clear. John Bowers for president!

[@mod_123_]

you just saved my life, thank you

[@bryanarmijos5159]

BEST VIDEO HANDS DOWN. Subbed!

[@fahdfayed1825]

First comment of my 10 years on youtube. Thank god for your existence.

[@yazidhanniche1064]

thank you , you saved my life

[@Utopus11]

Thank you, helped me a lot!

[@user-mo1gh2kg9q]

This helped me big time for preparing the mid term. Thanks!

[@mse312]

same , I have my midterm next week

[@sareenabaig8751]

7 years later... thank you!!!

[@deanbeebe74]

Seriously helpful - thank you so much!

[@johnbowers5447]

Glad it was helpful!

[@hotchocolate123]

great explanation ! thanks a lot

[@adolfocarrillo248]

Thanks for sharing your knowledge, I got it.🎉

[@tejaskashyap1392]

Great video! Saved me on my final!

[@zoe7886]

you, my friend, are a SAINT thank you

[@AuraRazor]

this was very helpful, thanks

[@superwendel]

Thanks a lot ! Very simple and useful !!

[@Stevofolife]

best example so far!

[@jeroen3648]

Thank you for this video , it helped me to solve recurrence relations

[@deveshsingh1479]

beautifully done

[@qR7pK9sJ2t]

Extraordinary....Thank u Sir..Love from India
#WeIndiaWeWin

[@daminatownes124]

Thanks this was really helpful!

[@turi104]

good explanation. made this method very clear.thankyou

[@Oh_ahhh_hangee]

Thank you so much, it helps me a lot! ^^

[@hemihobo]

Great walk through thank you

[@aditi3586]

omg thanks for this explanation!!

[@PapaDragon750]

Loved it. Thanks

[@clovisgu57]

crystal clear! thank you!

[@rahulkher8207]

I'll be honest, I was NOT expecting the O(n log n) bomb at the end.

[@Amy-tw3zh]

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)

[@Twannnn01]

@@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).

[@lasseskaalum6258]

@@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/

[@johnbowers5447]

That O(n log n) thing is sneaky. Can't turn your back for a second or it'll get you.

[@datim8540]

Insane video🙏🏻

[@krishnarathod6389]

Thank you..It is helpful...keep uploading

[@sahrishaltafkhan5041]

Thank You so much this is really helpful

[@asadmehmood408]

This was helpful please upload more examples to solved recurance...

[@TinieblaOscura]

You are the real MVP

[@muhammadumairkhan8435]

Thank you very for making it so easy for me.

[@kanelindsay4995]

Very good practical example compared to the bad slideshow video lecture version offered at my university.

[@noamansaleem3755]

Awesome Bestest Video on Sbstitution Method

[@aigerimzhanabayeva9909]

very very helpful!

[@tanvirwaseer16]

The most intuitive way I think this one is.

[@samanthafuquay6010]

Thank you for this video !!!

[@derekliu8867]

yep, this is the best vid on repeated sub hands down

[@johnbowers5447]

Thanks!

[@RosieSuh]

You are the best, ever

[@justinm2015]

Thank you sir that was really helpful

[@sabazubair9971]

thnx . this is the best video for recurrence

[@Azanali-kq5uy]

Really I understand very well

[@MrAlbashiri]

you are the best. thank you very much for the amazing video

[@VladTheLycan]

Thanks a lot mate !

[@Fr33xII]

Thank you so much

[@abdelrahmanmostafa4925]

good job man excellent

[@aditric]

You're awesome!

[@rohitmaurya4328]

THANKS.......its helps me a lot

[@khangpiano549]

Thank You!

[@louerleseigneur4532]

thanks a lot brother

[@korany07]

wow explanation is GOOD AF