Table of Contents:

The Problem Introduction                                                                   0:00 - 0:42
Analyzing Grade School Multiplication                                             0:42 - 2:09
How Do We Think About Doing Better?                                            2:09 - 3:06
Ok...Can We Do Better?                                                                       3:06 - 3:30
Let's Try A Divide & Conquer Approach                                            3:30 - 4:22
Redefining x & y In Terms of Our Segments                                     4:22 - 6:11
Multiplying The New Definitions Together                                       6:11 - 6:53
We Now Have An Equation For The Decomposition                      6:53 - 8:14
Raw Divide & Conquer Approach: Exact Additions                         8:14 - ...
Establishing The Worst Length From Multiplications                    8:44 - 9:24
Handling The 2 Multiplications On The Edge                                  11:15 - 13:47
End of "Raw Divide & Conquer Approach: Exact Additions"                13:47
Raw Divide & Conquer Approach: Recurrence                                13:47 - 16:43
Raw Divide & Conquer Approach: Solving The Recurrence           16:43 - 21:50
Raw Divide & Conquer Approach: Summing The Work                  21:50 - 23:37
A Breakthrough: Karatsuba's Insight & Analyzing Additions         23:37 - 27:18
Karatsuba's Algorithm: Recurrence                                                   27:18 - 28:14
Karatsuba's Algorithm: Solving The Recurrence                             28:14 - 30:28
Karatsuba's Algorithm: Summing The Work                                    30:28 - 31:17
How Did Karatsuba's Do?                                                                    31:17 - 32:48
Wrap Up                                                                                                  32:48 - 33:50


Mistakes:
31:20 -> O(n ^ lg(3) ) is the asymptotic bound on the additions. Karatsuba's does not do this exact amount of additions in the worst case since constants were dropped. If you look at the equation on the board, it can be further simplified to see that there will be constants in front of the atomic multiplication symbol.
Update -> There is O(n*log(n)) integer multiplication now: https://hal.archives-ouvertes.fr/hal-02070778/document

Karatsuba multiplication is not the fastest method for multiplication. Wikipedia: "The Toom–Cook algorithm is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm is even faster, for sufficiently large n."

when he speaks amharic i started searching for another opened chrome tab

my heart jumped when I heard him speak Amharic lol but loved the content. glad to have come across this channel, a new fan!

Wow Ethiopiawi  neh ende ...
Keep it up bro you are incredible

his free course is far better than the many paid courses of some giant educational company

When the video started I was like, "OK, it's time to open the subtitles." LOL. But as always, great video and a very articulate explanation. Thanks!

This was very informative, appreciate it.

This was extremely helpful. Thank you!

Wow, I feel miserable. That was my algorithms year project, 4 years ago and i totally forgot it and forgot its logic along with those Latin letters and yet I'm here stumbled upon this video while i'm preparing for my interview at Amazon.

Love your work and the effort.
Keep it up dude.

I am having this in my algorithm class, this really helped me!!!

Great explanation,
cleared many of the queries!
thanks a lot

Thank you so much! Really rescued me and i like your positive vibe!

Thank you! I could not bear whatch my profs dull video-lectures on this topic anymore, im happy i found someone enthusiastically explaining this by examples!

I had struggles with the medium level questions but after watching your videos, they don't seem confused anymore. I am going to purchase the one year subscription of you website.

Thank you so much.  I wish my professor had watched this before attempting to teach it.  Just brilliant.

I couldn't understand much because of the language difference but the graphics helped me, thanks
sorry i don't have good english

You are amazing man. Thank you so much for this

Excellent explanation

Best explanation of Karatsuba algorithm. Thank you very much.😊

Very nice explanation , very nice work , and when I see detailed description of the video and in comment ,really hard working man !! Keep it up ! And thank you very much for this kind of explanation 🙌🙌🙌