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.

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.

[Bonzo]

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.

[bigboykazmi]

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

[alanbiju]

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

[electricwatches]

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

[gerritgerritsen]

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

[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.

[fuudonanma]

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.

[luizlencioni]

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

[MorganAriel]

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

[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.

[jesusalejandrorodriguezgar]

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

[hydrophobicwalrus]

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

[ToasTeR]

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

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

[CaptainJellyBS]

Can I just have you as my algorithms professor?

[mundapakistani]

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

[GreeeenT]

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

[MrAbbasalrassam]

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

[dilaragoral]

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