Substitution method | Solving Recurrences | Data Structure & Algorithm | Appliedroots

Chapter Name: Solving Recurrences

[haha]

I have been out of school for 10 years. I re-read CLRS and multiple other difference sources about this substitution method. I just forgot too much about induction that I could not follow those other explanations. This video really did a great job of explaining this very convincingly and clearly without assuming any knowledge of the audience. Great job, kudos and I appreciate your work so much!

[natepardee]

Man I wish I had seen this prior to my algorithms midterm exam. The prof just uses the examples from the textbook, but the way you explain the steps make it so much clearer to understand. I will definitely be using you as a resource from now on

[yigithansaglam]

Bro, thanks a lot. I've been trying to understand this shit for all day long and you just made me figure it out.

[xbygmur]

I watched five or so videos on the subject and this was the clearest by far. Thank you!

[kashif-ghafoor]

that's what I exactly wanted from YouTube. Thanks a lot

[dolibert]

Easy understandable and extensive.
Thanks!

[nirajkc]

For someone having hard time to guess the solution in one go, I recommend you to go through master's method first before stepping into this one.
Btw great lesson!

[kevinmccarty]

Is the assumption "all" m<n is correct as by definition big-oh states n >= n0? Hence might there exist m < n0 where the condition does not hold? Perhaps "some" m<n is more accurate where n0 <= m < n. You can then set n > 2 * n0 and then let m be 1/2 n. Assuming the lower bound of m is n0, the rest should follow.

[exoticme]

Wow thank you so much, your a life savior 😢

[VishalSingh-rlwz]

One of best video on substitution method.
Thank you ❤

[xinmingd]

Great explanation! It would be better if you also showed the base case proof.

[MegaJolaus]

Thank you so much. This was super helpful.

[rushic]

Thank youn a lot!!, I was searching for something like this since 2 days

[tahabimuhammad]

Special thanks for showing an example by taking a wrong guess value and explaining the pitfalls.

[kairiannah]

seriously mate thank you! you deserve more than my lecturers!!!

[StudyAbroadWithMark]

My major problem has always been how to make the guess in the first place.
Anyway thanks for this video.

[zerobit]

Does anyone knows what happened in this example?

Give the recurrence relation.
T(n) = 2T(n/2) + 1

Guess : T(n) = O(n) ===>>> T(n) <= cn

To prove : T(n) <= cn, assume T(m) <= cm for all m < n.
let m = n/2 so T(m) <= cn/2

T(n) = 2T(n/2) + 1 <= 2*cn/2 + 1 = cn + 1 > cn.
So here is a contradiction with the guess, thus the T(n) = O(n) is wrong.

But we could also use Master theorem to prove that T(n) = O(n). So why there is a discrepancy?

Thanks~
Best regards.

[nar]

Thanks for this video, I learned about inductive proofs just a while ago, where it was about proving that P(k+1) holds using P(k) (P = proposition)

So the explanation of using T(n/2) to show that T(n) holds was helpful. (Well, not T(n) but whatever was used with T(n), in this case, the inequality)

*Correct me if I interpreted something incorrectly here

Have you perhaps also made a video about repeated backward substitution? I learned about it in a lecture but the CLRS didn't cover it. If not, can you make a recommendation, where it will be explained as well as you did here?

[ignassablinskas]

Note: without a base case you can't conclude anything using induction.

[vyxyfch]

for 13:30 is it not possible to change it into cn -(-n) so the (-n) can be excluded hence it will prove that T(n) <_ cn ?