Тёмный

Master Theorem Visually Explained 

Lars Quentin
Подписаться 423
Просмотров 36 тыс.
50% 1

Here we go over the intuition behind the master theorem / master method, which often times gets lost behind all the math required for the proof.
Visualized with Manim Community.
Sources and further links:
[Al Gore Clip, Simpsons episode 113](simpsons.fando...)
[Animating Fluid Sediment Mixture in Particle-Laden Flows]( • [SIGGRAPH 2018] Animat... )
[Control Strategies for Physically Simulated Characters Performing Two-player Competitive Sports]( • Control Strategies for... )
---
[Bubble-sort with Hungarian ("Csángó") folk dance]( • Bubble-sort with Hunga... )
[Insert-sort with Romanian folk dance.flv]( • Insert-sort with Roman... )
[Merge-sort with Transylvanian-saxon (German) folk dance.flv]( • Merge-sort with Transy... )
[Quick-sort with Hungarian (Küküllomenti legényes) folk dance.flv]( • Quick-sort with Hungar... )
[Select-sort with Gypsy folk dance.flv]( • Select-sort with Gypsy... )
[Shell-sort with Hungarian (Székely) folk dance.flv]( • Shell-sort with Hungar... )
---
[Model Checking](en.wikipedia.o...)
[Hoare Calculus](www.researchga...)
[Z3: An Efficient SMT Solver](doi.org/10.100...)
---
[What Is Big O Notation?]( • What Is Big O Notation? )
[Khan Academy: Asymptotic notation](www.khanacadem...)
---
[The Hammer Party - Divide And Conquer]( • Video )
[PINK GUY - HELP]( • PINK GUY - HELP )
[Look at this graph]( • Video )
[JO1 - Algorithm ]( • JO1|'Algorithm' PERFOR... )
---
[How Karatsuba's algorithm gave us new ways to multiply]( • How Karatsuba's algori... )
[2. Divide & Conquer: Convex Hull, Median Finding]( • 2. Divide & Conquer: C... )
[Geometry of football (Voronoi)]( • Geometry of football (... )
[3. Divide & Conquer: FFT]( • 3. Divide & Conquer: FFT )
[The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?]( • The Fast Fourier Trans... )
[FFT Example: Unraveling the Recursion]( • FFT Example: Unravelin... )
[4. Divide & Conquer: van Emde Boas Trees]( • 4. Divide & Conquer: v... )
[Closest Pair of Points (Divide and Conquer) Explained]( • Closest Pair of Points... )
[Strassen algorithm](en.wikipedia.o...)

Опубликовано:

 

4 окт 2024

Поделиться:

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 78   
@stefano3618
@stefano3618 4 месяца назад
In 5:26 I haven't understood why the index of the sum is from j=0 to log b (n-1) rather than j=0 ti log b (n) - 1
@larsquentin8249
@larsquentin8249 4 месяца назад
Sorry for the late reply. Because the last/n-th term are the leaves, which are the term afterwards, i.e. Theta(n^(log_b(a)))
@stefano3618
@stefano3618 3 месяца назад
It' s fine. I mean if we don't consider the last level in the summation we should do height minus 1, with height = log_b(n), so the minus 1 is outside the bracket. Correct me if I am wrong
@larsquentin8249
@larsquentin8249 3 месяца назад
@@stefano3618 Didn't see it again haha. Yes, you are completely correct, it should be sum_{j=0}^{log_b(n)-1} I've pinned your comment for everyone else. Thank you so much!
@chinglemba9136
@chinglemba9136 11 месяцев назад
it's a crime that your channel does not have millions of subscribers. THANK YOU for this
@Kaorii1905
@Kaorii1905 4 месяца назад
I agree
@West_Waktole
@West_Waktole 4 месяца назад
with only 2 videos?
@abhirup619
@abhirup619 Год назад
Everywhere I searched they just used the formula or showed how to use the formula! This is EXACTLY what I was looking for. Brilliant work
@LarryBordo
@LarryBordo 2 года назад
I had a really hard time understanding the Master Theorem when I was studying Algorithms so long ago. You've made understanding this complex formula so much easier. Thank you.
@xLany
@xLany 10 месяцев назад
Lars why are you so cool. This is one of the best algorithm teaching videos I've ever seen in my life. I’m relearning Master’s Theorem at 2am right now. Every couple mins I audibly say “what the f!!!” and pause the video to take agitated paces around the room because something you said just blew my mind again. Thank you for the clear explanation, the visualization, the scattered meme-ry, and the montage of cool applications at the end (I dropped so many "what the f"s going through that). Above all THANK YOU for all the time and care you put into this video, it is a cut above everything else I've seen!!!
@stark.aritra
@stark.aritra 9 месяцев назад
I have never seen such an eloquent explanation of the master theorem in books or any videos, hats off.
@sarumanork-orphanage5612
@sarumanork-orphanage5612 16 дней назад
Look at this graph! Perfect! Just as I was nodding off, you caught my attention again!
@jmagmdc
@jmagmdc Месяц назад
2:50 Nickelback.. this made my day
@tauheedakbar3781
@tauheedakbar3781 Год назад
absolutely beautiful work, really appreciate all the hard work you clearly put into this
@hayden4127
@hayden4127 Месяц назад
you explained master theorem 10 times better than our CS professor, this is soooo underrated!
@AyanKhan-dc3eu
@AyanKhan-dc3eu Год назад
Best video on master's theorem ! Thank You so much for this.
@redj_dev
@redj_dev 11 месяцев назад
confirmed best vid on YT about this. Saved my homework grade ty bb
@stefano3618
@stefano3618 3 месяца назад
thank you so much for the video. I really appreciate it: the topic is well and CLEARLY explained with fantastic animation.
@fynalph
@fynalph 2 месяца назад
Thanks for the Video Lars. It helped me a lot.
@tatox2167
@tatox2167 8 месяцев назад
brrrruuuuh you need to create more videos this was awesome
@speedwagon1524
@speedwagon1524 9 месяцев назад
You saved my Master's Degree! Thanks Lars, I love you!!!
@NigelSoh
@NigelSoh Месяц назад
This is such a great and helpful video. Very clear explanation... thanks Lars!! 🙌
@aryan-y4o6n
@aryan-y4o6n 7 месяцев назад
I think you are a kind person
@maxschikofski251
@maxschikofski251 Год назад
Very well visualised. Good Job, Lars!
@hainsh
@hainsh 2 месяца назад
Damnnn I love these channels with horrible mic but extraordinary content
@brunomoreira6416
@brunomoreira6416 6 месяцев назад
please make more videos, engaging, easy to understand and funny, great job!
@phillipsmith4220
@phillipsmith4220 Год назад
What an incredible video. I would have saved so much time if I had found this video first! Thank you so much.
@Trohnald
@Trohnald 7 месяцев назад
I LOVE YOU LARS THIS HAS BEEN SO HELPFUL
@Tiniku
@Tiniku Год назад
where have you been all my life. thank youu!
@samarthtandale9121
@samarthtandale9121 10 месяцев назад
Really awesome explanation brother ... kudoes!!! You diserve so many subs!
@emanabdelhaleem7561
@emanabdelhaleem7561 9 месяцев назад
This is just amazing work! Thank you so much.
@kingshukcs
@kingshukcs 9 месяцев назад
Very good presentation and I loved your style of teaching!!
@lukam.7575
@lukam.7575 Год назад
great video, well explained and well made, making it very easy to visualize the concepts being apllied to the problems.
@powermax6391
@powermax6391 6 месяцев назад
first time finally understanding it, thanks a lot
@7phanthony8
@7phanthony8 22 дня назад
yeeeaaaah this explanation is glorious.
@yunoletmehaveaname
@yunoletmehaveaname Год назад
Omg please post more videos. I love this!
@RyanNene-g9k
@RyanNene-g9k 2 дня назад
Thanks Lars Quentin!
@arniedeb2305
@arniedeb2305 Год назад
Holy fuck this is high quality, I'm surprised you don't have more subs
@王里昂-g9t
@王里昂-g9t Год назад
nice video man! Good explaination on the master theorem!
@ejsafara456
@ejsafara456 Год назад
this is such a good explanation! :D thank you, i finally understand ^^
@williamyang8408
@williamyang8408 4 месяца назад
This is so op wtf how do you only have 300 subs
@Ned_.
@Ned_. 6 месяцев назад
great video, thanks bro
@JS-dn9cr
@JS-dn9cr 6 месяцев назад
make more vids pleaseeeeee this is god tier
@johnwang41
@johnwang41 Год назад
U are amazing, I hope u can continue to do this, it is wonderful viode.
@sonikaagarwal931
@sonikaagarwal931 4 месяца назад
why do you only have one video??? i was so hoping to look at more :( but thanks anyway! great video
@wannabehuman.production
@wannabehuman.production 3 месяца назад
May you live a long happy life
7 месяцев назад
What a great video!
@kevalgandhi9162
@kevalgandhi9162 Год назад
Best Video so far on MT
@haiphan8360
@haiphan8360 8 месяцев назад
Time-efficient at its best!
@aryan-y4o6n
@aryan-y4o6n 8 месяцев назад
brilliantly explained
@lethalbacon3299
@lethalbacon3299 Год назад
Please! PLEASE MAKE NEW VIDEOS ABOUT OTHER COMPUTER SCIENCE TOPICS! This video war really great and I understood the Theorem!
@maxbill1921
@maxbill1921 Год назад
This is Wonderfull.... Best explanation
@notchicken
@notchicken Год назад
This makes things so clear. Wow.
@a.m.4154
@a.m.4154 7 месяцев назад
3:55 - "what is the depth of our tree?" - No such thing exists. You have the depth of a node, the height of a node, and the height of a tree.
@ilayohana3150
@ilayohana3150 6 месяцев назад
🤓even professors would say the depth of the tree to refer to the deepest point of the tree
@xash3000
@xash3000 8 месяцев назад
Thank you
@gabriel-oc4pt
@gabriel-oc4pt Год назад
bro I owe you one THANK YOU
@jurycould4275
@jurycould4275 Год назад
Bitte ende nicht als 0815-Entwickler. Das ist meine Domäne.
@mostafayounes9490
@mostafayounes9490 6 месяцев назад
Thank You❤
@sillaceestekay2069
@sillaceestekay2069 Год назад
You sir are a legend!
@anik._.
@anik._. 9 месяцев назад
brilliant
@neutral_positron
@neutral_positron Месяц назад
I think the only problem is your accent is hard to understand for the masses. Otherwise I see no reason why you don't have at least 500K subs.
@wyatt3112
@wyatt3112 7 месяцев назад
This is amazing. Thank you so much, Lars. Do you post videos anywhere else? I am studying "Introduction to Algorithms" by Cormen right now in school but I am much more a visual learner. Does anyone have any good playlists or outside resources to help with this material? I know a lot of folks really take to Abdul Bari's videos but I don't understand his explanations as easily as others seem to.
@theali8oras274
@theali8oras274 Год назад
thank you for this , my prof is garbage and im having a hard time with math
@gabut1839
@gabut1839 6 месяцев назад
YOUR VIDEO IS AMAZING, BE CONSISTENT AND ULL BLOW UP SIR!
@silentco2254
@silentco2254 Год назад
can you provide your code for the animation in manim I am new to manim and I would really learn a lot from you
@bryanshaong2333
@bryanshaong2333 8 месяцев назад
Where more video, hw due tmr , need help
@justavine487
@justavine487 Год назад
Very strong video. You could have a bigger audience if you also uploaded your videos in german ;)
@rea5782
@rea5782 2 года назад
Notification gang ☑ we lit 🔥
@wolfgangamadeusmozart3200
@wolfgangamadeusmozart3200 11 месяцев назад
Why you have ONLY ONE video ???
@spooki9813
@spooki9813 8 месяцев назад
dude thank you for this video i explained this to some autistic girl at a party and she went home w me :)
@JenniRocket
@JenniRocket 2 года назад
Damn man I finally really get it 😂
@visionz831
@visionz831 Год назад
3:16 What does he say here ? Subtitles please
@theali8oras274
@theali8oras274 Год назад
automatic subs help. they get it right at 3:16
@adityagujaria2598
@adityagujaria2598 2 года назад
Hey nice video.!!!
@srinivasbodduru4263
@srinivasbodduru4263 Месяц назад
bro work on the accent a little bit it is a little hard to understand
@ellenkoning3491
@ellenkoning3491 Год назад
to few people have seen this!
@mikhailwebb8377
@mikhailwebb8377 Год назад
I see that you are trying to explain as best as you can, but I still don't understand. The other videos on RU-vid for Master Theorem are also garbage.
Далее
What P vs NP is actually about
17:58
Просмотров 100 тыс.
The Mandelbrot Set
15:30
Просмотров 2 млн
The 360-Page Proof That 1+1=2
6:03
Просмотров 1,7 млн
Big-O Notation - For Coding Interviews
20:38
Просмотров 483 тыс.
How do QR codes work? (I built one myself to find out)
35:13
Researchers thought this was a bug (Borwein integrals)
17:26