Sign inSign in
ConceptSystems & CS

Karatsuba multiplication

A divide-and-conquer algorithm for multiplication that reduces the number of single-digit multiplications from four to three.
Watch it explained

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

2

Each in their own terms, from the easiest level.

  • Srini Devadas

    MIT · Undergraduate

    An algorithm that reduces four sub-multiplications to three using mathematical tricks, yielding a T(n) = 3T(n/2) + θ(n) recurrence and θ(n1.58)\theta(n^{1.58}) complexity.
    • 12:16Square Roots, Newton's Method

Connections

5

The lectures that define it or assume it, and the concepts next to it.

Concepts3

Lectures2

2 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.