After learning how to do it today, here's my first go at using the #manim library to create an animation explaining a #math concept. Although here I suppose it is more a #computerscience or analysis of #algorithms concept.
I haven't provided any context in the animation (I ran out of coding+compiling steam once the core explanation was satisfactory to me). It highlights the key ideas and terms for the three primary cases of the Master theorem for solving recurrences. It is not the most general form, but is perhaps the easiest/most useful form for an undergrad to grasp.
Allows analyzing recursive algorithms which split a problem with input size 𝑛 into 𝑎 subproblems, each of size 𝑛/𝑏 and spends 𝑛ᶜ time to perform the splitting into subproblems and/or recombining of subproblem solutions to get the overall solution.
The final runtime depends on 𝑐 and on what is often called the critical exponent \(\log_b (a)\). When teaching, I often frame it as let these two fight and whoever wins will dominate the runtime. If it is a draw, they compromise by throwing an extra log𝑛 term in there. At least that's my mnemonic.