My prof spent two hours trying to explain this and no one understood. In 6 minutes you successfully explained something that took my prof two hours to fuck up. Nice job, thank you.
Super helpful example! The only thing that wasn't in this video was why exactly each level splits into two. Turns out it's because for this kind of recurrence equation, of the form " a * T(b) + c " we have: 'a' is the number of times the recurrence is called [in this case "2" because *2*T(n/2) ], 'b' is the input size (usually n/2) and 'c' is the number of operations per iteration (in this case 4n).
Very nicely explained, with proper mathematical reasoning! I have watched both substitution and tree videos. It would be great if you also make one on the master method. Thanks!
I think that it's worth noting that each node splits into two branches due to the "2T" part of the recurrence. If it were 3T then there would be three branches from each node, etc.
If the coefficient is bigger than 3 it's still doable but if the branches grow at the same rate. The key is to find the height of the tree for the asymptotic runtime and if the branches grow at different rates then I usually take the one that grows fastest then use the substitution method to verify. Easier said than done of course. CLR 3rd Edition has an example like this.
*Start out with what you're given (in this case T(n)), and start the tree with everything that is not the recursive call. *Do the next recursive call (what's in the parenthesis). *Keep doing this until you find a pattern in terms of i. *Set the n value for the base case equal to your pattern that you have in parenthesis. *Solve for i *Do a summation from i=0 to what you found i to be equal to, and this summation is connected to the value at the top of your tree. *Multiply the top of tree value by (your i value + 1). Still a major pain in the ass, but this video definitely helps!
I have watched several tutorials before this and they all fall short when explaining how they derived their equations from the tree. You did an excellent job here of explaining what your method was. Thanks man!
I was thinking it's just me who thins CLRS makes things look extremely complicated... I'm relieved to see comments about it. Anyways thanks a lot for the explanation
In this case everything is good, but other students need to know that in general, the sum goes from i=0 to (last level)-1, because the last level doesn't cost as much as the other levels generally, cause it's a base case
This is strictly true, agreed. Though the base case can always be thought of as some constant. So if you care about EXACTLY what your recurrence sums to, you have to be careful, and I chose base cases that are easier to deal with. But if you really care about what order of growth (the O(f(n)), instead of the f(n)) your recurrence T(n) belongs in, then it actually doesn’t matter-because changing the base cases, or changing the tree by some constant number of levels, only has the effect of changing the answer by a constant factor or lower ordered terms, so you’ll still land on the correct order of function.
Far better than my useless professor. If they had handed me the subjects I could've gotten my entire degree just watching people like you on UA-cam. Thanks alot
This was a great explanation, I do have a question if anyone can answer it, please feel free to. I understand that in this example we are summing up 4n from i=0 to i = log(n), but where is the + 1 term from log(n) + 1 come from (time stamp 5:24). Why eas the + 1 term needed?
Nevermind I just saw the comment below. If anyone is wondering I will paste what @John Bowers said: "If you compute the sum of 1 from i=0 up to some value m, then the result is m+1. For instance let m=2. Then I have i = 0, i = 1, and i = 2; and so if I'm just summing up 1 for each of those index i values, I get 1 + 1 + 1 = 3. So sum_{i=0}^m 1 = m+1. If I count starting at 1 instead of at 0, then you don't get the +1: sum_{i=1}^m = m. "
Its videos like this that make wonder why I empty my wallet for school every quarter. Teacher spent an hour on this and you did it better (and cheaper) in 6 minutes.
I have a question please... I have this equation that I'm supposed to solve with the tree method: T(n) = 4T(n/2) + n^2*log (n) I am not given a base case, how can I figure it out?
So basically we added 4n log base 2 of n times that makes sense. And another question we don't have to count Recurring call to the function itself when calculating time complexity..??
best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best explanation thank you sir.
At 5:21, do you mean the sum equals log2n, or goes 4n + 4n ... + log2n? Don't understand what mean by log2n in the curly brackets. Also confused as to why you decided to convert the sum at the end.
I think the idea is to get it to an equation, so that would explain why he converted the sum at the end. However, I'm a little confused on where the extra +1 came from lol.
If T(1) = 4 shouldn’t you solve for 4 = 2/n^i? I thought when you are solving for height you use the actual base case. I don’t understand why you do T(1) = 1. (Minute 4:29). Please help
Good point. The T(1)=4 base case is contrived so that the leaves of the tree have the same values as the internal nodes (i.e. 4n). If the base case does not agree with the non-recursive part of the main recurrence, then you have to be a bit more careful, take your tree only down to the level just above the leaf nodes, and then handle the leaf nodes in a separate step (which is just number of leaves * base case value).
1 = n/2^i *=>* 2^i = n "i" is the power of 2 and to make "i" the subject, by using the exp. and log. properties(to bring something _down_ from "power" you gotta do _log_ of something on the other side of the equal sign, which is "n"), it becomes *log(n)* and 'cause "i" was the *power* of 2, it's log *2* (n). Thus, *i = log2(n)* Hope it helped :)
I was following along, and I thought well, but I don't understand how you conclude that it will terminate when 1 = n/2^i..? You imply it's obvious but I don't get it
Bro.....in recursion, you stop when you arrive at a problem to which you know solution right???? In this case, it is T(1). You already know solution for it....so, it is the base case, you stop there
now i am more confused how is he making two recursive calls from the 4n i am doing a question in which there are three recursive calls now i am confused man
My prof spent two hours trying to explain this and no one understood. In 6 minutes you successfully explained something that took my prof two hours to fuck up. Nice job, thank you.
I feel this 4 years later...
Literally, same here.... Prof spent 2 hours and I didn't understand a single thing. I watched the first 2 mins of this and understood everything.
You did in 6 minutes what my professor could not do in an entire lecture. Thank you so much for clearly explaining the summation step.
Yes.
@@dasdawidt No.
CLRS makes it unnecessarily complicated. This clears it up. Thanks!
glad im not the only one
I think all textbooks are unnecessarily complicated... However, that book especially is.. yes..
I agree with that
3 years later, Im here, after reading the CLRS.
@@cycv5881 mee too, 5 days later your 3 days later. i have algorithm exam this may
the best explanation of divide and conquer recurrence relation on youtube. Why is this so low in youtube search ranking?
i year later it is still underrated. this is the best thing i saw today
thank you, this is the best explanation i could find in youtube.
Glad it helped.
Super helpful example! The only thing that wasn't in this video was why exactly each level splits into two. Turns out it's because for this kind of recurrence equation, of the form " a * T(b) + c " we have: 'a' is the number of times the recurrence is called [in this case "2" because *2*T(n/2) ], 'b' is the input size (usually n/2) and 'c' is the number of operations per iteration (in this case 4n).
So does 'a' refer to the number of branches at each level?
Very nicely explained, with proper mathematical reasoning! I have watched both substitution and tree videos. It would be great if you also make one on the master method. Thanks!
I think that it's worth noting that each node splits into two branches due to the "2T" part of the recurrence. If it were 3T then there would be three branches from each node, etc.
If the coefficient is bigger than 3 it's still doable but if the branches grow at the same rate. The key is to find the height of the tree for the asymptotic runtime and if the branches grow at different rates then I usually take the one that grows fastest then use the substitution method to verify. Easier said than done of course. CLR 3rd Edition has an example like this.
Great job John. You are teaching the concepts the way they are meant to be taught.
Still helping in 2024
*Start out with what you're given (in this case T(n)), and start the tree with everything that is not the recursive call.
*Do the next recursive call (what's in the parenthesis).
*Keep doing this until you find a pattern in terms of i.
*Set the n value for the base case equal to your pattern that you have in parenthesis.
*Solve for i
*Do a summation from i=0 to what you found i to be equal to, and this summation is connected to the value at the top of your tree.
*Multiply the top of tree value by (your i value + 1).
Still a major pain in the ass, but this video definitely helps!
I have watched several tutorials before this and they all fall short when explaining how they derived their equations from the tree. You did an excellent job here of explaining what your method was. Thanks man!
Great explanation. I couldn't find a simple and clear guide like yours.
Helped a lot! Thanks
Loved the comparison of the summation to a for loop. Thanks!
You bet!
This man deserves a salute
Awesome explaintation (Y)
I was thinking it's just me who thins CLRS makes things look extremely complicated... I'm relieved to see comments about it. Anyways thanks a lot for the explanation
saving lives to this day. Thank You
For once i have understood the tree method and substitution method. THANKS A MILLION!
Glad it helped!
You make it so simple, thank you so much ! it's just perfectly clear
Damn WHAT YOU DID HERE IS MAGIC.
In this case everything is good, but other students need to know that in general, the sum goes from i=0 to (last level)-1, because the last level doesn't cost as much as the other levels generally, cause it's a base case
This is strictly true, agreed. Though the base case can always be thought of as some constant. So if you care about EXACTLY what your recurrence sums to, you have to be careful, and I chose base cases that are easier to deal with. But if you really care about what order of growth (the O(f(n)), instead of the f(n)) your recurrence T(n) belongs in, then it actually doesn’t matter-because changing the base cases, or changing the tree by some constant number of levels, only has the effect of changing the answer by a constant factor or lower ordered terms, so you’ll still land on the correct order of function.
@@johnbowers5447 thank you!
Far better than my useless professor. If they had handed me the subjects I could've gotten my entire degree just watching people like you on UA-cam. Thanks alot
kollalo mwone....funny tanne
This was the least complicated explanation. Thanks a lot.
I like your voice and the way you explain. God bless.
The most precise and best example on the UA-cam. Thanks a lot sir :) Lots of love from Pakistan
Master's and Iteration videos please!!!!! Best recurrence explanations available on youtube ryt now for sure!!!!
wow thank you for the video! I learned this in class but now it's much clearer
Wow, now I dont have to worry about my exams tomorrow anymore! Thank you, you have saved my life! Like, really!
Thank you so much. Now I finally have hope again and I see perspective for my life. Now I can step on to solving the towers of Hanoi.
This was a great explanation, I do have a question if anyone can answer it, please feel free to. I understand that in this example we are summing up 4n from i=0 to i = log(n), but where is the + 1 term from log(n) + 1 come from (time stamp 5:24). Why eas the + 1 term needed?
Nevermind I just saw the comment below. If anyone is wondering I will paste what @John Bowers said:
"If you compute the sum of 1 from i=0 up to some value m, then the result is m+1. For instance let m=2. Then I have i = 0, i = 1, and i = 2; and so if I'm just summing up 1 for each of those index i values, I get 1 + 1 + 1 = 3.
So sum_{i=0}^m 1 = m+1. If I count starting at 1 instead of at 0, then you don't get the +1: sum_{i=1}^m = m. "
@@ramziadil8613 thank youuu!
Wow man this was the best explanation so far...
Glad to hear it!
I'm grateful I found this video, wow.
Good explanation. You should make playlist of videos it will help in channel growth
Good idea. I've gotta add it to my to-do list :).
Its videos like this that make wonder why I empty my wallet for school every quarter. Teacher spent an hour on this and you did it better (and cheaper) in 6 minutes.
A six minute video do much much much better than my lecturer! What's wrong with our education....
perfect explanation, clear to understand
very very good explained , thanks Batman
Got everything in the first attempt. Thanks!
Thanks for this video! I'm just confused why you wrote the base case equals 1 and not 4. If someone could explain I'd appreciate it!
Mayn! youre just amazing! i was so freakin confused about it, but you saved the day. I hope I nail my exam as well. love xx
Thanks Man! This was really nice explanation
You made it easy. Greatly thankful to you for this easy explanation.
Best explanation ever. Thanks you. You are a life saver.
why does 4n/2 have 2 recursive calls? jesus you gotta explain every step man
because of the 2 beside the recursive call as in 2T(n/2).
if it was 3T(n/3), it would have three recursive calls each of n/3
Tq u soo mch sir before i had lot of doubts on these topic nw i am ready to solve any problem in these topic nice lecturer tq u sirrr
Thanks! This was quite helpful for my algorithms analysis homework.
ambada
Thank you, you are the best.
I am waiting more tutorials for you ;)
where did you get the +4n at the end?
so clear and easy explanation! thanks
wow what a explanation...i love it ..please make more videos to help others ❤❤
You are awesome man.!! Thanks for this video..I have been reading coreman for hours to understand this :(.!!
you are a life saver!
Thank you. This helped clear some things up.
short, helpful, and sweet.
best explanation ever
This was amazingly helpful
You really made this easy for me !!!
What a perfect explanation. Thank you so much!!
Thank you so much i can finally step forward in life.
Very easy explanation, thanks:)
I think for 2^i the total cost has to be 2^i*T(1) which will be 2^i*(4)
more videos on recurrence please
very clear presentation, thanks.
You sir.. deserve to be a professor at MIT.
Thank you so much!
Thanks a lot. But I want to ask just one thing, what about the term = 2(T(n/2))
good explanation sir..it really helped me
what a helpful video god bless you
I have a question please... I have this equation that I'm supposed to solve with the tree method:
T(n) = 4T(n/2) + n^2*log (n)
I am not given a base case, how can I figure it out?
It's been 3 years, figured it out yet?
T(n)=
Excellent explanation !! Thank you
Really well done
Best explaination
Great Video's..I wish you could show the Master Method or Mater Theorem also?
loooooool
So basically we added 4n log base 2 of n times that makes sense.
And another question we don't have to count
Recurring call to the function itself when calculating time complexity..??
great explanation!
Thanks, John.
best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best best explanation thank you sir.
Отличное объяснение!
Спасибо, господин Президент!
Can you please do some more recurrence tree problems
Best explanation! Thanks
It was really helpful thanks
At 5:21, do you mean the sum equals log2n, or goes 4n + 4n ... + log2n? Don't understand what mean by log2n in the curly brackets. Also confused as to why you decided to convert the sum at the end.
I think the idea is to get it to an equation, so that would explain why he converted the sum at the end. However, I'm a little confused on where the extra +1 came from lol.
easy, understandable explanation, thanks!!!!
wew
Great video, thank you for your time! What kind of pen do you use?
Cello ballpoint pen - Blue.
Love from MIT 🥰
please tutor me. my class is using CLRS and idk what's going on
God bless you.
If T(1) = 4 shouldn’t you solve for 4 = 2/n^i? I thought when you are solving for height you use the actual base case. I don’t understand why you do T(1) = 1. (Minute 4:29). Please help
Loved it, Thank You :)
thank you for the amazing video
*amazon
thanks for the nice explanation :)
Thanks. Great Video.
You do not use T(1) =4 at all here, as if the answer would be the same if T(1) = 500.
Good point. The T(1)=4 base case is contrived so that the leaves of the tree have the same values as the internal nodes (i.e. 4n). If the base case does not agree with the non-recursive part of the main recurrence, then you have to be a bit more careful, take your tree only down to the level just above the leaf nodes, and then handle the leaf nodes in a separate step (which is just number of leaves * base case value).
What if there's no base case? How do I decide one?
Why log2(n) ? Everything is understandable except the number of levels.
Sayan Sarkar look up exponential and logarithmic properties. He doesn't explain it but he basically flipped the fraction into a log.
1 = n/2^i *=>* 2^i = n
"i" is the power of 2 and to make "i" the subject, by using the exp. and log. properties(to bring something _down_ from "power" you gotta do _log_ of something on the other side of the equal sign, which is "n"), it becomes *log(n)* and 'cause "i" was the *power* of 2, it's log *2* (n). Thus, *i = log2(n)*
Hope it helped :)
Really helpful, thanks a lot!!!!
I was following along, and I thought well, but I don't understand how you conclude that it will terminate when 1 = n/2^i..? You imply it's obvious but I don't get it
Bro.....in recursion, you stop when you arrive at a problem to which you know solution right????
In this case, it is T(1).
You already know solution for it....so, it is the base case, you stop there
Awesome❤
Master method with recurrence make video plz
now i am more confused how is he making two recursive calls from the 4n i am doing a question in which there are three recursive calls now i am confused man