Memoization to Speed Up Recursion; The Master Theorem
2We did about two hours of lab time today to let students write a recursive program to compute the super Fibonacci sequence (where you add three numbers together instead of two) using bigints. The recursive algorithm is easy to write, but suffers from an exponential running time. Oof. But since it is going to be computing the same values over and over, we can create a little cache to write down the answer any time we compute a value, and if we are ever asked to compute that value again, we can just use the cached value instead. This speeds it up from exponential running time to linear - nice!
We then talked about the Master Theorem (sometimes called the Master Method) which will tell you the Big O running time of a certain class of recursive algorithms. You have to compute three values:
A: How many times the function calls itself
B: What fraction of work (B is the *denominator*) goes to each of the sub-calls
C: How much work is done at each level in terms of O(N^C). C is the exponent! So for constant running time, C is 0, for linear, C is 1, for N^2, C is 2, etc.
You then compare log(base B)(A) and C, and use the formula to get the Big O running time of the algorithm
Other Videos By Bill Kerney
| 2021-11-08 | Parasocial Relationships, Cognitive Biases |
| 2021-11-06 | ACM Workshop: Minecraft Modding |
| 2021-11-05 | Unordered Maps + ELO Coding Competition |
| 2021-11-05 | Corporate Censorship |
| 2021-11-05 | Master Theorem Part 2 |
| 2021-11-05 | Linear Algebra for Video Games - Vector x Scalar, Matrix x Vector, Transformation Matrices |
| 2021-11-04 | Networking in C++ with TCP Streams |
| 2021-11-04 | The Impact of Social Media |
| 2021-11-03 | Raytracing Explained in 40 minutes |
| 2021-11-02 | All The Things in QuakeC (and UE4!) |
| 2021-11-02 | Memoization to Speed Up Recursion; The Master Theorem |
| 2021-11-01 | Making an Attendance System Part 2 |
| 2021-11-01 | Making an Attendance System Part 1 |
| 2021-11-01 | Making a Movie in Scratch |
| 2021-10-31 | Racism in Facial Recognition Databases |
| 2021-10-31 | Reading Code (C++) |
| 2021-10-29 | The best Team Fortress 1 map (Rock2) + Overview of Where Code is in QuakeC |
| 2021-10-28 | Proof By Induction Part 2 |
| 2021-10-28 | Explaining Triangle Rasterization in 30 Minutes |
| 2021-10-27 | Racism and Computer Science |
| 2021-10-27 | Making an Image Filter in C++ Version 1 |