Opening Complexity of Basic Arithmetic
Complexity of Basic Arithmetic
- Length
- 27 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Complexity of addition
O'Donnell multiplies integers through the Fast Fourier Transform, reaching linear time on the Word RAM model.
The time complexity of basic arithmetic operations provides a foundation for manipulating large numbers in cryptography and algorithms. Starting with grade school addition and its word-level acceleration, the analysis moves to the core problem of integer multiplication and the limitations of the standard quadratic algorithm. Through divide-and-conquer methods and the Fast Fourier Transform, multiplication speeds up to near-linear time on the Word RAM model. The lecture concludes by surveying how other operations, such as division, square roots, and GCD, reduce directly to the time complexity of multiplication.
The time complexity of basic arithmetic operations provides a foundation for manipulating large numbers in cryptography and algorithms. Starting with grade school addition and its word-level acceleration, the analysis moves to the core problem of integer multiplication and the limitations of the standard quadratic algorithm. Through divide-and-conquer methods and the Fast Fourier Transform, multiplication speeds up to near-linear time on the Word RAM model. The lecture concludes by surveying how other operations, such as division, square roots, and GCD, reduce directly to the time complexity of multiplication.
Modern Computer Arithmetic
The Art of Computer Programming, Volume I, Section 4.3.3.C
Integer multiplication

This lecture
Lecture 18 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in
The Art of Computer Programming, Volume 2
The Art of Computer Programming, Volume 1
Integer multiplication in time O(n log n)