For folks interested in multiplication algorithms (turns out this is a big deal in computer science and math).

1. High school method O(n^2)
2. Karatsuba O(n^1.58)
3. ToomCook O(n^1.46)
4. FFT O(n*log(n)*log(log(n)))

The last algorithm is pretty complex. We explain the intuition behind it in this video.

00:00 Who should watch this?
00:18 Example Problem
01:23 Karatsuba Algorithm
02:38 Time complexity analysis
03:57 ToomCook Algorithm
04:48 Problem Polynomial Multiplication
05:27 Plotting points on a graph
05:57 Plotting nth degree curve
07:00 Multiplication Strategy
07:28 Optimisation Strategy
08:50 Choosing the right points
09:25 Complex Numbers!
10:26 The nth roots of unity
12:56 The impact of complex numbers
14:57 FFT Conclusion
15:52 Thank you!

InterviewReady: https://interviewready.io/
Karatsuba: https://en.wikipedia.org/wiki/Karatsu...
ToomCook: https://en.wikipedia.org/wiki/Toom%E2...
FFT: https://en.wikipedia.org/wiki/Sch%C3%...

You can follow me on:
Github: https://github.com/InterviewReady/sys...
Twitter:   / gkcs_  

#SystemDesign #InterviewReady #Coding