The following tables list the computational complexity of various algorithms for common mathematical operations.
Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.[1] See big O notation for an explanation of the notation used.
Note: Due to the variety of multiplication algorithms,
M(n)
This table lists the complexity of mathematical operations on integers.
Operation | Input | Output | Algorithm | Complexity | ||||
---|---|---|---|---|---|---|---|---|
Addition | Two n | One n+1 | Schoolbook addition with carry | \Theta(n) | ||||
Subtraction | Two n | One n+1 | Schoolbook subtraction with borrow | \Theta(n) | ||||
Multiplication | Two n | One 2n | Schoolbook long multiplication | Od\left(n2\right) | ||||
Karatsuba algorithm | Od\left(n1.585\right) | |||||||
3-way Toom–Cook multiplication | Od\left(n1.465\right) | |||||||
k |
\right) | |||||||
Mixed-level Toom–Cook (Knuth 4.3.3-T) | Od\left(n2\sqrt{2 | |||||||
Schönhage–Strassen algorithm | Od\left(nlognloglogn\right) | |||||||
Harvey-Hoeven algorithm[2] [3] | O(nlogn) | |||||||
Division | Two n | One n | Schoolbook long division | Od\left(n2\right) | ||||
Burnikel–Ziegler Divide-and-Conquer Division[4] | O(M(n)logn) | |||||||
Newton–Raphson division | O(M(n)) | |||||||
Square root | One n | One n | Newton's method | O(M(n)) | ||||
Modular exponentiation | Two n k | One n | Repeated multiplication and reduction | Od\left(M(n)2k\right) | ||||
Exponentiation by squaring | O(M(n)k) | |||||||
Exponentiation with Montgomery reduction | O(M(n)k) |
On stronger computational models, specifically a pointer machine and consequently also a unit-cost random-access machine it is possible to multiply two -bit numbers in time O(n).[5]
Here we consider operations over polynomials and denotes their degree; for the coefficients we use a unit-cost model, ignoring the number of bits in a number. In practice this means that we assume them to be machine integers.
Operation | Input | Output | Algorithm | Complexity |
---|---|---|---|---|
Polynomial evaluation | One polynomial of degree n | One number | Direct evaluation | \Theta(n) |
Horner's method | \Theta(n) | |||
Polynomial gcd (over Z[x] F[x] | Two polynomials of degree n | One polynomial of degree at most n | Euclidean algorithm | Od\left(n2\right) |
Fast Euclidean algorithm (Lehmer) | O(M(n)logn) |
Many of the methods in this section are given in Borwein & Borwein.[6]
The elementary functions are constructed by composing arithmetic operations, the exponential function (
\exp
log
\sin,\cos
\exp
log
Below, the size
n
Algorithm | Applicability | Complexity | |
---|---|---|---|
Taylor series
\exp(2x)=[\exp(x)]2 | \exp,log,\sin,\cos,\arctan | Od\left(M(n)n1/2\right) | |
Taylor series; FFT-based acceleration | \exp,log,\sin,\cos,\arctan | Od\left(M(n)n1/3(logn)2\right) | |
Taylor series; binary splitting + bit-burst algorithm[7] | \exp,log,\sin,\cos,\arctan | Od\left(M(n)(logn)2\right) | |
Arithmetic–geometric mean iteration[8] | \exp,log,\sin,\cos,\arctan | O(M(n)logn) |
It is not known whether
O(M(n)logn)
(M(n))
Function | Input | Algorithm | Complexity | |
---|---|---|---|---|
Gamma function | n | Series approximation of the incomplete gamma function | Od\left(M(n)n1/2(logn)2\right) | |
Fixed rational number | Hypergeometric series | Od\left(M(n)(logn)2\right) | ||
m/24 m | Arithmetic-geometric mean iteration | O(M(n)logn) | ||
Hypergeometric function {}p\ | F_q | n | (As described in Borwein & Borwein) | Od\left(M(n)n1/2(logn)2\right) |
Fixed rational number | Hypergeometric series | Od\left(M(n)(logn)2\right) |
This table gives the complexity of computing approximations to the given constants to
n
Constant | Algorithm | Complexity | |
---|---|---|---|
Golden ratio, \phi | Newton's method | O(M(n)) | |
Square root of 2, \sqrt{2} | Newton's method | O(M(n)) | |
Euler's number, e | Binary splitting of the Taylor series for the exponential function | O(M(n)logn) | |
Newton inversion of the natural logarithm | O(M(n)logn) | ||
Pi, \pi | Binary splitting of the arctan series in Machin's formula | Od\left(M(n)(logn)2\right) | |
Gauss–Legendre algorithm | O(M(n)logn) | ||
Euler's constant, \gamma | Sweeney's method (approximation in terms of the exponential integral) | Od\left(M(n)(logn)2\right) |
Algorithms for number theoretical calculations are studied in computational number theory.
Operation | Input | Output | Algorithm | Complexity | |
---|---|---|---|---|---|
Greatest common divisor | Two n | One integer with at most n | Euclidean algorithm | Od\left(n2\right) | |
Binary GCD algorithm | Od\left(n2\right) | ||||
Left/right k-ary binary GCD algorithm[9] |
| ||||
Stehlé–Zimmermann algorithm[10] | O(M(n)logn) | ||||
Schönhage controlled Euclidean descent algorithm[11] | O(M(n)logn) | ||||
Jacobi symbol | Two n | 0 -1 1 | Schönhage controlled Euclidean descent algorithm[12] | O(M(n)logn) | |
Stehlé–Zimmermann algorithm[13] | O(M(n)logn) | ||||
Factorial | A positive integer less than m | One O(mlogm) | Bottom-up multiplication | Od\left(M\left(m2\right)logm\right) | |
Binary splitting | O(M(mlogm)logm) | ||||
Exponentiation of the prime factors of m | O(M(mlogm)loglogm) O(M(mlogm)) | ||||
Primality test | A n | True or false | AKS primality test | Od\left(n6+o(1)\right) O(n3) | |
Elliptic curve primality proving | Od\left(n4+\varepsilon\right) | ||||
Baillie–PSW primality test | Od\left(n2+\varepsilon\right) | ||||
Miller–Rabin primality test | Od\left(kn2+\varepsilon\right) | ||||
Solovay–Strassen primality test | Od\left(kn2+\varepsilon\right) | ||||
Integer factorization | A b | A set of factors | General number field sieve | Od\left((1+\varepsilon)b\right) | |
Shor's algorithm | O(M(b)b) | ||||
See main article: Computational complexity of matrix multiplication. The following complexity figures assume that arithmetic with individual elements has complexity O(1), as is the case with fixed-precision floating-point arithmetic or operations on a finite field.
Operation | Input | Output | Algorithm | Complexity | |||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Matrix multiplication | Two n x n | One n x n | Schoolbook matrix multiplication | O(n3) | |||||||
Strassen algorithm | Od\left(n2.807\right) | ||||||||||
Coppersmith–Winograd algorithm (galactic algorithm) | Od\left(n2.376\right) | ||||||||||
Optimized CW-like algorithms (galactic algorithms) | Od\left(n\psi=2.3728596\right) | ||||||||||
Matrix multiplication | One n x m one m x p | One n x p | Schoolbook matrix multiplication | O(nmp) | |||||||
Matrix multiplication | One n x \left\lceilnk\right\rceil one \left\lceilnk\right\rceil x n k\geq0 | One n x n | Algorithms given in [22] | O(n\omega(k)+\epsilon) \omega(k) | |||||||
Matrix inversion | One n x n | One n x n | Gauss–Jordan elimination | Od\left(n3\right) | |||||||
Strassen algorithm | Od\left(n2.807\right) | ||||||||||
Coppersmith–Winograd algorithm | Od\left(n2.376\right) | ||||||||||
Optimized CW-like algorithms | Od\left(n\psi\right) | ||||||||||
Singular value decomposition | One m x n | One m x m one m x n one n x n | Bidiagonalization and QR algorithm | Od\left(m2n\right) ( m\geqn | |||||||
One m x n one n x n one n x n | Bidiagonalization and QR algorithm | Od\left(mn2\right) ( m\leqn | |||||||||
QR decomposition | One m x n | One m x n one n x n | Algorithms in [23] |
\right) ( m\geqn | |||||||
Determinant | One n x n | One number | Laplace expansion | O(n!) | |||||||
Division-free algorithm[24] | Od\left(n4\right) | ||||||||||
LU decomposition | O(n3) | ||||||||||
Bareiss algorithm | Od\left(n3\right) | ||||||||||
Fast matrix multiplication[25] | Od\left(n\psi\right) | ||||||||||
Back substitution | Triangular matrix | n | Back substitution[26] | Od\left(n2\right) | |||||||
Characteristic polynomial | One n x n | One degree- n | Faddeev-LeVerrier algorithm | O(n\psi+1) |
In 2005, Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Chris Umans showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2.[27]
Algorithms for computing transforms of functions (particularly integral transforms) are widely used in all areas of mathematics, particularly analysis and signal processing.
Operation | Input | Output | Algorithm | Complexity |
---|---|---|---|---|
Discrete Fourier transform | Finite data sequence of size n | Set of complex numbers | Schoolbook | O(n2) |
Fast Fourier transform | O(nlogn) |
O(M(n)logn)
\varepsilon>0
O
|
b(logb)2}\right).