- 2
- 42 622
Lars Quentin
Приєднався 1 лип 2021
Master Theorem Visually Explained
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.fandom.com/wiki/Grampa_vs._Sexual_Inadequacy)
- [Animating Fluid Sediment Mixture in Particle-Laden Flows](ua-cam.com/video/kt_TlUsv6rU/v-deo.html)
- [Control Strategies for Physically Simulated Characters Performing Two-player Competitive Sports](ua-cam.com/video/KIaYFt6qY7E/v-deo.html)
---
- [Bubble-sort with Hungarian ("Csángó") folk dance](ua-cam.com/video/semGJAJ7i74/v-deo.html)
- [Insert-sort with Romanian folk dance.flv](ua-cam.com/video/EdIKIf9mHk0/v-deo.html)
- [Merge-sort with Transylvanian-saxon (German) folk dance.flv](ua-cam.com/video/dENca26N6V4/v-deo.html)
- [Quick-sort with Hungarian (Küküllomenti legényes) folk dance.flv](ua-cam.com/video/kDgvnbUIqT4/v-deo.html)
- [Select-sort with Gypsy folk dance.flv](ua-cam.com/video/0-W8OEwLebQ/v-deo.html)
- [Shell-sort with Hungarian (Székely) folk dance.flv](ua-cam.com/video/yn0EgXHb5jc/v-deo.html)
---
- [Model Checking](en.wikipedia.org/wiki/Model_checking)
- [Hoare Calculus](www.researchgate.net/figure/Hoare-logic-with-separation-logic-for-reasoning-about-execution-time_fig2_324458680)
- [Z3: An Efficient SMT Solver](doi.org/10.1007/978-3-540-78800-3_24)
---
- [What Is Big O Notation?](ua-cam.com/video/Q_1M2JaijjQ/v-deo.html)
- [Khan Academy: Asymptotic notation](www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation)
---
- [The Hammer Party - Divide And Conquer](ua-cam.com/video/hJrSPMtTq4E/v-deo.html)
- [PINK GUY - HELP](ua-cam.com/video/Ho1LgF8ys-c/v-deo.html)
- [Look at this graph](ua-cam.com/video/sIlNIVXpIns/v-deo.html)
- [JO1 - Algorithm ](ua-cam.com/video/VnLscLX1BQ8/v-deo.html)
---
- [How Karatsuba's algorithm gave us new ways to multiply](ua-cam.com/video/cCKOl5li6YM/v-deo.html)
- [2. Divide & Conquer: Convex Hull, Median Finding](ua-cam.com/video/EzeYI7p9MjU/v-deo.html)
- [Geometry of football (Voronoi)](ua-cam.com/video/ZAz9mDlsWgQ/v-deo.html)
- [3. Divide & Conquer: FFT](ua-cam.com/video/iTMn0Kt18tg/v-deo.html)
- [The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?](ua-cam.com/video/h7apO7q16V0/v-deo.html)
- [FFT Example: Unraveling the Recursion](ua-cam.com/video/Ty0JcR6Dvis/v-deo.html)
- [4. Divide & Conquer: van Emde Boas Trees](ua-cam.com/video/hmReJCupbNU/v-deo.html)
- [Closest Pair of Points (Divide and Conquer) Explained](ua-cam.com/video/6u_hWxbOc7E/v-deo.html)
- [Strassen algorithm](en.wikipedia.org/wiki/Strassen_algorithm)
Visualized with Manim Community.
Sources and further links:
- [Al Gore Clip, Simpsons episode 113](simpsons.fandom.com/wiki/Grampa_vs._Sexual_Inadequacy)
- [Animating Fluid Sediment Mixture in Particle-Laden Flows](ua-cam.com/video/kt_TlUsv6rU/v-deo.html)
- [Control Strategies for Physically Simulated Characters Performing Two-player Competitive Sports](ua-cam.com/video/KIaYFt6qY7E/v-deo.html)
---
- [Bubble-sort with Hungarian ("Csángó") folk dance](ua-cam.com/video/semGJAJ7i74/v-deo.html)
- [Insert-sort with Romanian folk dance.flv](ua-cam.com/video/EdIKIf9mHk0/v-deo.html)
- [Merge-sort with Transylvanian-saxon (German) folk dance.flv](ua-cam.com/video/dENca26N6V4/v-deo.html)
- [Quick-sort with Hungarian (Küküllomenti legényes) folk dance.flv](ua-cam.com/video/kDgvnbUIqT4/v-deo.html)
- [Select-sort with Gypsy folk dance.flv](ua-cam.com/video/0-W8OEwLebQ/v-deo.html)
- [Shell-sort with Hungarian (Székely) folk dance.flv](ua-cam.com/video/yn0EgXHb5jc/v-deo.html)
---
- [Model Checking](en.wikipedia.org/wiki/Model_checking)
- [Hoare Calculus](www.researchgate.net/figure/Hoare-logic-with-separation-logic-for-reasoning-about-execution-time_fig2_324458680)
- [Z3: An Efficient SMT Solver](doi.org/10.1007/978-3-540-78800-3_24)
---
- [What Is Big O Notation?](ua-cam.com/video/Q_1M2JaijjQ/v-deo.html)
- [Khan Academy: Asymptotic notation](www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation)
---
- [The Hammer Party - Divide And Conquer](ua-cam.com/video/hJrSPMtTq4E/v-deo.html)
- [PINK GUY - HELP](ua-cam.com/video/Ho1LgF8ys-c/v-deo.html)
- [Look at this graph](ua-cam.com/video/sIlNIVXpIns/v-deo.html)
- [JO1 - Algorithm ](ua-cam.com/video/VnLscLX1BQ8/v-deo.html)
---
- [How Karatsuba's algorithm gave us new ways to multiply](ua-cam.com/video/cCKOl5li6YM/v-deo.html)
- [2. Divide & Conquer: Convex Hull, Median Finding](ua-cam.com/video/EzeYI7p9MjU/v-deo.html)
- [Geometry of football (Voronoi)](ua-cam.com/video/ZAz9mDlsWgQ/v-deo.html)
- [3. Divide & Conquer: FFT](ua-cam.com/video/iTMn0Kt18tg/v-deo.html)
- [The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?](ua-cam.com/video/h7apO7q16V0/v-deo.html)
- [FFT Example: Unraveling the Recursion](ua-cam.com/video/Ty0JcR6Dvis/v-deo.html)
- [4. Divide & Conquer: van Emde Boas Trees](ua-cam.com/video/hmReJCupbNU/v-deo.html)
- [Closest Pair of Points (Divide and Conquer) Explained](ua-cam.com/video/6u_hWxbOc7E/v-deo.html)
- [Strassen algorithm](en.wikipedia.org/wiki/Strassen_algorithm)
Переглядів: 42 452
Great explanation! I love the connection you make between recursion tree and master theorem, that makes the thing much clear.
Fucking amazing
brooooo you are coooll af
al gore rizzms
After spending at least 3 hours checking the rest links you shared to get the basics I was able to understand this video. Kudos for the great work. Really appreciate it. Unfortunately, in academic level, there is the attitude of trying to confuse someone instead of explaining and this is where gems like this video bring light to the journey of Algos 😁
so helpful! and you cited your sources!! T_T 🐐🐐🐐 thanks.
Thanks Lars Quentin!
Look at this graph! Perfect! Just as I was nodding off, you caught my attention again!
yeeeaaaah this explanation is glorious.
2:50 Nickelback.. this made my day
bro work on the accent a little bit it is a little hard to understand
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.
you explained master theorem 10 times better than our CS professor, this is soooo underrated!
This is such a great and helpful video. Very clear explanation... thanks Lars!! 🙌
Thanks for the Video Lars. It helped me a lot.
Damnnn I love these channels with horrible mic but extraordinary content
May you live a long happy life
thank you so much for the video. I really appreciate it: the topic is well and CLEARLY explained with fantastic animation.
This is so op wtf how do you only have 300 subs
why do you only have one video??? i was so hoping to look at more :( but thanks anyway! great video
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
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)))
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
@@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!
great video, thanks bro
YOUR VIDEO IS AMAZING, BE CONSISTENT AND ULL BLOW UP SIR!
first time finally understanding it, thanks a lot
make more vids pleaseeeeee this is god tier
please make more videos, engaging, easy to understand and funny, great job!
Thank You❤
What a great video!
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.
🤓even professors would say the depth of the tree to refer to the deepest point of the tree
I think you are a kind person
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.
I LOVE YOU LARS THIS HAS BEEN SO HELPFUL
Where more video, hw due tmr , need help
brilliantly explained
Time-efficient at its best!
Thank you
dude thank you for this video i explained this to some autistic girl at a party and she went home w me :)
brrrruuuuh you need to create more videos this was awesome
This is just amazing work! Thank you so much.
Very good presentation and I loved your style of teaching!!
I have never seen such an eloquent explanation of the master theorem in books or any videos, hats off.
brilliant
You saved my Master's Degree! Thanks Lars, I love you!!!
Really awesome explanation brother ... kudoes!!! You diserve so many subs!
No context, no explanation, just donut
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!!!
Why you have ONLY ONE video ???
confirmed best vid on YT about this. Saved my homework grade ty bb <3
it's a crime that your channel does not have millions of subscribers. THANK YOU for this
I agree
with only 2 videos?
I see that you are trying to explain as best as you can, but I still don't understand. The other videos on UA-cam for Master Theorem are also garbage.