ConceptSystems & CS
Karatsuba multiplication
A divide-and-conquer algorithm for multiplication that reduces the number of single-digit multiplications from four to three.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Asymptotic complexity1Divide and conquer algorithm1Divide and conquer multiplication1Multiplication1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Srini Devadas
An algorithm that reduces four sub-multiplications to three using mathematical tricks, yielding a T(n) = 3T(n/2) + θ(n) recurrence and complexity.
Connections
5The lectures that define it or assume it, and the concepts next to it.