Solved Recurrence Tree Method

[@michaelbowen4275]

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.

[@dasdawidt]

Yes.

[@kells9k]

@@dasdawidt No.

[@nile6017]

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.

[@coreytv1338]

I feel this 4 years later...

[@xdragonflame6563]

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.

[@ntcool123]

CLRS makes it unnecessarily complicated. This clears it up. Thanks!

[@sharma1337]

glad im not the only one

[@TheFotoGuys]

I think all textbooks are unnecessarily complicated... However, that book especially is.. yes..

[@mohammedthaier1718]

I agree with that

[@cycv5881]

3 years later, Im here, after reading the CLRS.

[@kobuki7788]

@@cycv5881 mee too, 5 days later your 3 days later. i have algorithm exam this may

[@christiansakai]

the best explanation of divide and conquer recurrence relation on youtube. Why is this so low in youtube search ranking?

[@ankitb3954]

i year later it is still underrated. this is the best thing i saw today

[@sayyidalisajjadrizavi7418]

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!

[@AbdulZurghani]

thank you, this is the best explanation i could find in youtube.

[@johnbowers5447]

Glad it helped.

[@tonesaft]

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

[@keion_arknights]

So does 'a' refer to the number of branches at each level?

[@rahuls331]

Great job John. You are teaching the concepts the way they are meant to be taught.

[@rayjennings1861]

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.

[@rayjennings1861]

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.

[@ninjababin0967]

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!

[@fuwuf5201]

Still helping in 2024

[@yoavk]

Great explanation. I couldn't find a simple and clear guide like yours. Helped a lot! Thanks

[@FinnPayton]

Loved the comparison of the summation to a for loop. Thanks!

[@johnbowers5447]

You bet!

[@patrickmayer9218]

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

[@iramshahzadi8875]

This man deserves a salute Awesome explaintation (Y)

[@tripasect1271]

I like your voice and the way you explain. God bless.

[@ThefamousMrcroissant]

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 KZbin. Thanks alot

[@abhijithkp818]

kollalo mwone....funny tanne

[@izzy2815]

For once i have understood the tree method and substitution method. THANKS A MILLION!

[@johnbowers5447]

Glad it helped!

[@busbusvlog]

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

[@douniazedbehloul5766]

You make it so simple, thank you so much ! it's just perfectly clear

[@muhammadumar1639]

The most precise and best example on the KZbin. Thanks a lot sir :) Lots of love from Pakistan

[@darshanasharma7781]

This was the least complicated explanation. Thanks a lot.

[@rahulpurohit2461]

Damn WHAT YOU DID HERE IS MAGIC.

[@azimjonilkhomov7785]

saving lives to this day. Thank You

[@mayankparihar7053]

Master's and Iteration videos please!!!!! Best recurrence explanations available on youtube ryt now for sure!!!!

[@SaviourFik934]

Wow, now I dont have to worry about my exams tomorrow anymore! Thank you, you have saved my life! Like, really!

[@dasdawidt]

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.

[@merylwang4193]

wow thank you for the video! I learned this in class but now it's much clearer

[@likithr.n9692]

Wow man this was the best explanation so far...

[@johnbowers5447]

Glad to hear it!

[@niloyabid2851]

I'm grateful I found this video, wow.

[@ramziadil8613]

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?

[@ramziadil8613]

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

[@manuelconte623]

@@ramziadil8613 thank youuu!

[@IPear]

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

[@johnbowers5447]

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.

[@IPear]

@@johnbowers5447 thank you!

[@pushparay5554]

You made it easy. Greatly thankful to you for this easy explanation.

[@anonInDE]

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?

[@stabnite]

It's been 3 years, figured it out yet?

[@abhijithkp818]

T(n)=

[@lubainakhan2862]

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

[@FernandoRodriguez-et7qj]

where did you get the +4n at the end?

[@adventurer2395]

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.

[@Pramerios]

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.

[@sirajAlam049]

Thanks a lot. But I want to ask just one thing, what about the term = 2(T(n/2))

[@nawnitsen7771]

Best explanation ever. Thanks you. You are a life saver.

[@maxstevens7951]

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.

[@AyaNori]

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!

[@gunaygultekin]

perfect explanation, clear to understand

[@davidwu3417]

A six minute video do much much much better than my lecturer! What's wrong with our education....

[@pluto5307]

very very good explained , thanks Batman

[@marekmenczer5493]

Thanks Man! This was really nice explanation

[@FernandoRomany]

Thank you, you are the best. I am waiting more tutorials for you ;)

[@devinshook3289]

This was amazingly helpful

[@jayrathod2172]

Good explanation. You should make playlist of videos it will help in channel growth

[@johnbowers5447]

Good idea. I've gotta add it to my to-do list :).

[@SaifUlIslam-di5xv]

Got everything in the first attempt. Thanks!

[@fireandbombs12]

Thanks! This was quite helpful for my algorithms analysis homework.

[@abhijithkp818]

ambada

[@chiharuyo]

Great video, thank you for your time! What kind of pen do you use?

[@AmanKumar-lm1ok]

Cello ballpoint pen - Blue.

[@Montyhack]

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

[@nikitapandey7719]

You really made this easy for me !!!

[@DarkLordAli95]

short, helpful, and sweet.

[@grow3384]

so clear and easy explanation! thanks

[@Ashmole3]

Thank you. This helped clear some things up.

[@Vupadhayay]

You are awesome man.!! Thanks for this video..I have been reading coreman for hours to understand this :(.!!

[@kiran10110]

What a perfect explanation. Thank you so much!!

[@kevin3d362]

you are a life saver!

[@ksrikanth1353]

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

[@abhishek-shrm]

Best explanation ever

[@shahidurrahman1804]

Very easy explanation, thanks:)

[@Pereki_]

Thank you so much i can finally step forward in life.

[@pkr1kajdjasdljskjdjsadjlaskdja]

wow what a explanation...i love it ..please make more videos to help others ❤❤

[@feisuxiaozhu]

very clear presentation, thanks.

[@mohamedfathi5551]

what a helpful video god bless you

[@vaibhavlodha5398]

Excellent explanation !! Thank you

[@kells9k]

Wow. Very succinct video man, thank you for making and posting it. Just to clarify, @ 0:21 are you saying "BESIDES the recursive call"? As in, in addition to...? Thanks

[@johnbowers5447]

Well, sorry I didn’t see this comment until now, but yes. A recurrence accounts for work done by a recursive function. It has the form T(n) = k T ( some function making n smaller) + g(n). This is for a recursive function that makes k recursive calls and surrounding those recursive calls does f(n) amount of additional work. The recurrence tree is basically a glorified spreadsheet for computing the total work done by all recursive calls. It does this by storing the “additional work” done by each call in the tree node, and the work done by each recursive call is pushed down into each sub-tree to account for.

[@aadil4236]

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

[@davidFbeckham]

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

[@swamysriman7147]

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

[@syedrizvi2687]

Thank you so much!

[@Daniel-iy1ed]

It was really helpful thanks

[@Pramerios]

What if there's no base case? How do I decide one?

[@harishrajora6453]

Can I have an example with uneven splits of the tree?

[@hagitamiga6069]

Really well done

[@AmanPatel-fo6dj]

Отличное объяснение!

[@johnbowers5447]

Спасибо, господин Президент!

[@sagarmoyganguly4140]

What if there are no other operations beside the recursive call at T(n) level?.... then what will the tree start with?... I just cant figure that out.

[@arpitajana9051]

good explanation sir..it really helped me

[@نوره-ر4ث7و]

Best explanation! Thanks

[@michaelmuse581]

Great explanation!

[@rockstar2596]

easy, understandable explanation, thanks!!!!

[@abhijithkp818]

wew

[@ahsaltwater]

Loved it, Thank You :)

[@fkhatri]

Thanks, John.

[@SamuelCherukuttyCheruvathur]

thanks for the nice explanation :)

[@MrAlbashiri]

thank you for the amazing video

[@abhijithkp818]

*amazon

[@chessmemes-]

please help me if the recurrence function is multiplied by a number other than 2 like 3 do I branch 3 times each layer ?

[@johnbowers5447]

Yes. The multiplicity of the recursive call gives you the branching factor in the recursion tree.

[@FrankLi92]

please tutor me. my class is using CLRS and idk what's going on

[@blackfromabove9383]

Really helpful, thanks a lot!!!!

[@uroobashahid8037]

more videos on recurrence please

[@ikkeshramanna6387]

so the big oh notation would be O(n log2 n) ?

[@tewodroskasahun8721]

I think for 2^i the total cost has to be 2^i*T(1) which will be 2^i*(4)

[@TruongNguyen-pl9cd]

why is at the end 1 = 4n?

[@habiburrehman7482]

Best explaination

[@dipenpatel5226]

Thanks. Great Video.

[@keemoyen8531]

Can you please do some more recurrence tree problems

[@Asmrnerd10]

You sir.. deserve to be a professor at MIT.

[@sayasark]

Why log2(n) ? Everything is understandable except the number of levels.

[@LetTheWritersWrite]

Sayan Sarkar look up exponential and logarithmic properties. He doesn't explain it but he basically flipped the fraction into a log.

[@fatimahz7182]

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 :)

[@MrAlbashiri]

[log2(n)+1] why did you add 1 at the end?

[@johnbowers5447]

See my response to @Arbi Themarajuwanabarbie below.

[@DanT-iu6oc]

why does 4n/2 have 2 recursive calls? jesus you gotta explain every step man

[@techduck123]

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

[@willturner3440]

Love from MIT 🥰