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

[@natepardee3792]

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

[@haha345]

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!

[@yigithansaglam9128]

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

[@kevinmccarty2967]

Is the assumption "all" m= n0? Hence might there exist m < n0 where the condition does not hold? Perhaps "some" m

[@nirajkc224]

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!

[@zeden3075]

Thank you sir, you taught this so much better than my professor 🙏

[@xinmingd8992]

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

[@Twannnn01]

I don't understand how you went from cnlog(n)-cn+n to cnlog(n), can you elaborate on that step? time: 8:41

[@clashingwithsahib]

according to me he is saying that this whole term (cnlog(n)-cn+n ) is less then cnlogn because we are subtracting (c-1)n from nlogn. therefore we just use this relation to get t(n) = cnlogn -(c-1)n to t(n)

[@k_e_n_n_y_mccormick]

this probably isnt worth much to you after 6 months, but here's a simple example: Take b as any number >= 0. x = 2 - 1b Therefore: x = 0)

[@sarahli2933]

@@clashingwithsahib But this argument is not valid if c is something between 0 and 1. Instead, I think the reason he discarded the linear term is because asymptotically they are trivial compared to O(nlgn).

[@Sagar_smh]

@@sarahli2933 Your reasoning seems more logical.

[@marcosadriano6245]

If you prove that a > b and b > c so you proved a > c. In this video a = nlgn, b = nlgn - (c - 1)n and c = T(n).

[@ShaneHughes-q1x]

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

[@StudyAbroadWithMark]

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

[@brrrrrrrrrr9313]

hello...i have exams in 2 days...did you get a better understanding on how to guess the answer or any other vdo you can link... please would it help a lot 🙏🙏

[@VishalSingh-rl8wz]

One of best video on substitution method. Thank you ❤

[@tahabimuhammad4524]

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

[@priyankand3692]

how to guess the time complexity ?

[@angadsinghvirdi5689]

@@priyankand3692 same doubt, do you now have the explanation for that?

[@kashif-ghafoor]

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

[@rushic24]

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

[@alanjesse5660]

Pro tip: watch movies on flixzone. Me and my gf have been using them for watching a lot of movies recently.

[@aldenraymond1781]

@Alan Jesse Yup, been using Flixzone for since december myself =)

[@amineb7833]

Who is Youn

[@dimaghkokholo5417]

Big O is n

[@pallina_di_neve]

good video to be honest, thank you and keep it up

[@zerobit778]

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)

[@noahmann1180]

Not sure if I entirely follow your question but basically cn is another way of giving bounds for O(n). For all intents and purposes cn=O(n) but we ignore the c because we are only looking for an upper bound when using BigO notation so we just ignore the constant. It is also worth noting that with the master method there are a few fringe cases in which cases where it does not work. Namely when the leaves (divide step) are almost equal but not equal to the root (conquer step) because both case 1 and case 3 require them to be polynomially smaller and larger respectively. Case 2 of the master method can generally absorb a difference of about log n but if it doesn't fit in that log n difference and it doesn't fit in case 1 or 3 as shown before it can't be used. Hoped this helped and I'm sorry if I confused you more!

[@RubLox_Live]

Youre using T(n) = 2T(n/2) + 1 vs the video using T(n) = 2T(n/2) + n which is completely different

[@perzillo]

At 8:41 , you say that the expression is less than or equal because -(c-1)n is negative. Should we specify that the c should be greater than one for it to hold? or is it enough to realize that there exists a c greater than 1 such that the proof holds?

[@Lichcrafter]

I think earlier he defined c as some constant greater than 0. Yeah, a 2:26

[@Lichcrafter]

Sorry, I misunderstood your question. I don't know, but I guess you are right in that it is enough for there to exist one C greater than 1.

[@iproiguess3528]

from the beginning, he said that the condition is there exists where c is bigger than 0, so you dont need to write it down. But it is good to write it down anyways.

[@dolibert]

Easy understandable and extensive. Thanks!

[@fahadfauzan5221]

how do you just guess correctly, there's so many options

[@adarshmaurya7553]

you can guess any complexity and then check if it is true, he used the correct guess to teach us. if you use O(n^2) it will also be true, but it's loosely bound.

[@kevinhoxha240]

Hi, in mathematical induction we typically have a base case. I was wondering how come we did not use it here? For example, do we need to show that it holds for T(1) or T(2) etc...

[@MegaJolaus]

Recurrence relations will usually have a recurrence T(n) specified for values greater than some n and a single value specified for T(1) or whatever the "base case" is (you might have seen the notation where you have T(n) = { "two lines for the two cases"). That T(1) would be the case where the recursion "bottoms out" and you would have for example just T(1) = 1. If you imagine a recursion tree, that is the cost of a single leaf at the bottom of the tree.

[@rohithanasuri8759]

Explained beautifully

[@talhaturkumozkurt8052]

Awesome teaching.

[@ngogaraul4155]

On the mistake example .if there is minus n was it going to be true

[@itz_me_imraan02]

If we get any new recurrence how will we guess correctly.....there are other videos too on substitution where they substitute the values and find the series.... dats more easy I guess....here it's more sort of proving the answer rather than finding the answer

[@信者の男]

Now I'm even more lost than I was before playing the video

[@낟-d1o]

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)

[@iproiguess3528]

you are comparing to previous statement, if -n then it will be greater than because you are subtracting. Thats what I think

[@erikOHsix06]

At 8:12, you said log2 is log 2 base 2 and changed it to 1. How did you know it was base 2? When I graph kx(logx - log2) and kx(logx - 1), I get two different graphs. How/why did you replace log2 with 1?

[@fsginsainity9327]

its not log, its lg. log is base 10, lg is base 2

[@na50r24]

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?

[@sandeshdalvi3781]

superb explanation sir

[@GATEAppliedCourse]

Thanks and welcome

[@josephzou360]

Amazing presentation u got a sub.

[@ignassablinskas9175]

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

[@falaksajjad4910]

in this example we have already know the T(n)=O(n logn) then we assume exist this .If does't know Then ?

[@adarshmaurya7553]

you can guess any complexity and then check if it is true, he used the correct guess to teach us. if you use O(n^2) which will also be true, but it's loosely bound.

[@bretstuart4161]

Can someone explain what m is? and why we choose it as n/2

[@exoticme4760]

Wow thank you so much , your a life savior 😢

[@Rockyzach88]

This helped a lot, thx. That being said, does it have to equal exactly? The reason cn + n is not cn because T(n) could be in between cn and n aka n(c+1). I have a similar problem where the f(n) in the recurrence is logn and you end up getting something like nlg^2(n) - nlgn + n (without the Cs) and the soln is O(nlg^2(n)), however it makes sense because while the nlgn grows faster, it's subtracting in this case and it's just obvious that nlg^2(n) grows faster than n. They do give a T(1) = 1. Are you supposed to use that somehow to finish the proof? NVM I see.

[@emperor8716]

the T(1)=1 makes things so much easier. i have to do some questions which don't even give that.

[@MegaJolaus]

Thank you so much. This was super helpful.

[@alperkaya8919]

thanks sir, it was a nice lecture

[@gabrielrocha1330]

Very well explained, thanks.

[@amitsamui4958]

superb explaination

[@RodrigoRocha-st7nm]

love u mate, that saved me

[@edoardodepiccoli3004]

thanks a lot

[@prathamhullamballi837]

The proof is incomplete. The result we proved was for n/2 >= n_0, which is n>=2n_0. What we needed was to prove the guess for n>=n_0, so we still aren't done with the problem. We need to show that the guess is true for n_0

[@iproiguess3528]

It might be me who does not understand. But in induction m is less than n since n is less than n +1, so this is big-oh notation naturally. Meanwhile n_0

[@trafalgarlaw9919]

Thank you for the explanation!

[@алексейфедоровичкарамазов]

I liked how you get to the point and explain very simply!!!

[@hell9659]

very bad explained, in such a hard way, without a true example. I swear i will make a video of how to solve by this method when i learn it

[@emperor8716]

i read this before watching so i assumed it would be a bad video but it actually explained well. i think you just don't have the prerequisite knowledge

[@rammus997]

@@emperor8716it is not bad, but he definitely jumps around a lot. Most people go fast with explanations because they expect fundamental understanding of core concepts(such as induction). This idea usually just leads to confusion since most people go to these videos because of their lack of understanding. A slower Way longer explanation void of expectations is far superior…

[@버그헌터_기브르]

Thank you good sir

[@Lan-sv6rt]

Thank you so much!

[@naeemkhan4534]

you should have taught back substitution as guessing is tough

[@mazenabouelhassen4913]

Thanks a lot!

[@viki8815]

How he guess this ,if i guess O(n) in place of O(nlgn) then what happened?

[@suchitmeshram9230]

Watch full video

[@adarshmaurya7553]

you can guess any complexity and then check if it is true, he used the correct guess to teach us. if you use O(n) it will return as false.

[@tashp]

Thank you!

[@ahmetkarakartal9563]

thank you so much

[@amitjajoo9510]

thanks

[@Yellowstone300]

very chaotic

[@iftikhar3609]

like

[@brianlee4966]

Thanks so much! This is really helpful.