Computational complexity of mathematical operations
The following tables list the computational complexity of various algorithms for common mathematical operations.
Arithmetic and algebraic functions
| Operation | Input | Output | Algorithm | Complexity |
|---|---|---|---|---|
| Addition | Two n-digit numbers | One n+1-digit number | Schoolbook addition | O(n) |
| Subtraction | Two n-digit numbers | One n+1-digit number | Schoolbook subtraction | O(n) |
| Multiplication | Two n-digit numbers |
One 2n-digit number | Schoolbook multiplication | O(n2) |
| Karatsuba multiplication | O(n1.585) | |||
| Toom-Cook multiplication | O(n1+ε) ε arbitrarily small | |||
| Schönhage-Strassen multiplication | O(n log n log log n) | |||
| Note: The complexity of multiplication will be referred to as M(n) below | ||||
| Division | Two n-digit numbers | One n-digit number | Schoolbook division | O(n2) |
| Newton's method | M(n) | |||
| Square root | One n-digit number | One n-digit number | Newton's method | M(n) |
| Polynomial evaluation | ? | ? | ? | ? |
Special functions
Number theory
Matrix algebra
The following complexity figures assume that arithmetic with individual elements has complexity O(1), as is the case with fixed-precision floating-point arithmetic.
| Operation | Input | Output | Algorithm | Complexity |
|---|---|---|---|---|
| Matrix multiplication | Two n×n-matrices | One n×n-matrix | Schoolbook matrix multiplication | O(n3) |
| Strassen algorithm | O(n2.807) | |||
| Coppersmith–Winograd algorithm | O(n2.376) | |||
| Matrix inversion | One n×n-matrix | One n×n-matrix | Gaussian elimination | O(n3) |