# Computational complexity of mathematical operations

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. See big O notation for an explanation of the notation used.
Note: Due to the variety of multiplication algorithms, $M(n)$ below stands in for the complexity of the chosen multiplication algorithm.

## Arithmetic functions

This table lists the complexity of mathematical operations on integers.
| Operation | Input | Output | Algorithm | Complexity |
| Addition | Two $n$-digit numbers | One $n+1$-digit number | Schoolbook addition with carry | $\Theta (n)$ |
| Subtraction | Two $n$-digit numbers | One $n+1$-digit number | Schoolbook subtraction with borrow | $\Theta (n)$ |
| Multiplication | Two $n$-digit numbers | One $2n$-digit number | Schoolbook long multiplication | $O{\mathord {\left(n^{2}\right)}}$ |
| Multiplication | Two $n$-digit numbers | One $2n$-digit number | Karatsuba algorithm | $O{\mathord {\left(n^{1.585}\right)}}$ |
| Multiplication | Two $n$-digit numbers | One $2n$-digit number | 3-way Toom–Cook multiplication | $O{\mathord {\left(n^{1.465}\right)}}$ |
| Multiplication | Two $n$-digit numbers | One $2n$-digit number | $k$-way Toom–Cook multiplication | $O{\mathord {\left(n^{\frac {\log(2k-1)}{\log k}}\right)}}$ |
| Multiplication | Two $n$-digit numbers | One $2n$-digit number | Mixed-level Toom–Cook (Knuth 4.3.3-T) | $O{\mathord {\left(n\,2^{\sqrt {2\log n}}\,\log n\right)}}$ |
| Multiplication | Two $n$-digit numbers | One $2n$-digit number | Schönhage–Strassen algorithm | $O{\mathord {\left(n\log n\log \log n\right)}}$ |
| Multiplication | Two $n$-digit numbers | One $2n$-digit number | Harvey-Hoeven algorithm | $O(n\log n)$ |
| Division | Two $n$-digit numbers | One $n$-digit number | Schoolbook long division | $O{\mathord {\left(n^{2}\right)}}$ |
| Division | Two $n$-digit numbers | One $n$-digit number | Burnikel–Ziegler Divide-and-Conquer Division | $O(M(n)\log n)$ |
| Division | Two $n$-digit numbers | One $n$-digit number | Newton–Raphson division | $O(M(n))$ |
| Square root | One $n$-digit number | One $n$-digit number | Newton's method | $O(M(n))$ |
| Modular exponentiation | Two $n$-digit integers and a $k$-bit exponent | One $n$-digit integer | Repeated multiplication and reduction | $O{\mathord {\left(M(n)\,2^{k}\right)}}$ |
| Modular exponentiation | Two $n$-digit integers and a $k$-bit exponent | One $n$-digit integer | Exponentiation by squaring | $O(M(n)\,k)$ |
| Modular exponentiation | Two $n$-digit integers and a $k$-bit exponent | One $n$-digit integer | 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 n-bit numbers in time O(n).

## Algebraic functions

Here we consider operations over polynomials and n 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$ with integer coefficients | One number | Direct evaluation | $\Theta (n)$ |
| Polynomial evaluation | One polynomial of degree $n$ with integer coefficients | One number | Horner's method | $\Theta (n)$ |
| Polynomial gcd (over $\mathbb {Z} [x]$ or $F[x]$) | Two polynomials of degree $n$ with integer coefficients | One polynomial of degree at most $n$ | Euclidean algorithm | $O{\mathord {\left(n^{2}\right)}}$ |
| Polynomial gcd (over $\mathbb {Z} [x]$ or $F[x]$) | Two polynomials of degree $n$ with integer coefficients | One polynomial of degree at most $n$ | Fast Euclidean algorithm (Lehmer) | $O(M(n)\log n)$ |

## Special functions

Many of the methods in this section are given in Borwein & Borwein.

### Elementary functions

The elementary functions are constructed by composing arithmetic operations, the exponential function ($\exp$), the natural logarithm ($\log$), trigonometric functions ($\sin ,\cos$), and their inverses. The complexity of an elementary function is equivalent to that of its inverse, since all elementary functions are analytic and hence invertible by means of Newton's method. In particular, if either $\exp$ or $\log$ in the complex domain can be computed with some complexity, then that complexity is attainable for all other elementary functions.
Below, the size $n$ refers to the number of digits of precision at which the function is to be evaluated.
| Algorithm | Applicability | Complexity |
| Taylor series; repeated argument reduction (e.g. $\exp(2x)=[\exp(x)]^{2}$) and direct summation | $\exp ,\log ,\sin ,\cos ,\arctan$ | $O{\mathord {\left(M(n)n^{1/2}\right)}}$ |
| Taylor series; FFT-based acceleration | $\exp ,\log ,\sin ,\cos ,\arctan$ | $O{\mathord {\left(M(n)n^{1/3}(\log n)^{2}\right)}}$ |
| Taylor series; binary splitting + bit-burst algorithm | $\exp ,\log ,\sin ,\cos ,\arctan$ | $O{\mathord {\left(M(n)(\log n)^{2}\right)}}$ |
| Arithmetic–geometric mean iteration | $\exp ,\log ,\sin ,\cos ,\arctan$ | $O(M(n)\log n)$ |
It is not known whether $O(M(n)\log n)$ is the optimal complexity for elementary functions. The best known lower bound is the trivial bound $\Omega$$(M(n))$.

### Non-elementary functions

| Function | Input | Algorithm | Complexity |
| Gamma function | $n$-digit number | Series approximation of the incomplete gamma function | $O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}$ |
| Gamma function | Fixed rational number | Hypergeometric series | $O{\mathord {\left(M(n)(\log n)^{2}\right)}}$ |
| Gamma function | $m/24$, for $m$ integer. | Arithmetic-geometric mean iteration | $O(M(n)\log n)$ |
| Hypergeometric function $_{p}\!F_{q}$ | $n$-digit number | (As described in Borwein & Borwein) | $O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}$ |
| Hypergeometric function $_{p}\!F_{q}$ | Fixed rational number | Hypergeometric series | $O{\mathord {\left(M(n)(\log n)^{2}\right)}}$ |

### Mathematical constants

This table gives the complexity of computing approximations to the given constants to $n$ correct digits.
| 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)\log n)$ |
| Euler's number, $e$ | Newton inversion of the natural logarithm | $O(M(n)\log n)$ |
| Pi, $\pi$ | Binary splitting of the arctan series in Machin's formula | $O{\mathord {\left(M(n)(\log n)^{2}\right)}}$ |
| Pi, $\pi$ | Gauss–Legendre algorithm | $O(M(n)\log n)$ |
| Euler's constant, $\gamma$ | Sweeney's method (approximation in terms of the exponential integral) | $O{\mathord {\left(M(n)(\log n)^{2}\right)}}$ |

## Number theory

Algorithms for number theoretical calculations are studied in computational number theory.
| Operation | Input | Output | Algorithm | Complexity |
| Greatest common divisor | Two $n$-digit integers | One integer with at most $n$ digits | Euclidean algorithm | $O{\mathord {\left(n^{2}\right)}}$ |
| Greatest common divisor | Two $n$-digit integers | One integer with at most $n$ digits | Binary GCD algorithm | $O{\mathord {\left(n^{2}\right)}}$ |
| Greatest common divisor | Two $n$-digit integers | One integer with at most $n$ digits | Left/right k-ary binary GCD algorithm | $O{\mathord {\left({\frac {n^{2}}{\log n}}\right)}}$ |
| Greatest common divisor | Two $n$-digit integers | One integer with at most $n$ digits | Stehlé–Zimmermann algorithm | $O(M(n)\log n)$ |
| Greatest common divisor | Two $n$-digit integers | One integer with at most $n$ digits | Schönhage controlled Euclidean descent algorithm | $O(M(n)\log n)$ |
| Jacobi symbol | Two $n$-digit integers | $0$, $-1$ or $1$ | Schönhage controlled Euclidean descent algorithm | $O(M(n)\log n)$ |
| Jacobi symbol | Two $n$-digit integers | $0$, $-1$ or $1$ | Stehlé–Zimmermann algorithm | $O(M(n)\log n)$ |
| Factorial | A positive integer less than $m$ | One $O(m\log m)$-digit integer | Bottom-up multiplication | $O{\mathord {\left(M\left(m^{2}\right)\log m\right)}}$ |
| Factorial | A positive integer less than $m$ | One $O(m\log m)$-digit integer | Binary splitting | $O(M(m\log m)\log m)$ |
| Factorial | A positive integer less than $m$ | One $O(m\log m)$-digit integer | Exponentiation of the prime factors of $m$ | $O(M(m\log m)\log \log m)$, $O(M(m\log m))$ |
| Primality test | A $n$-digit integer | True or false | AKS primality test | $O{\mathord {\left(n^{6+o(1)}\right)}}$ $O(n^{3})$, assuming Agrawal's conjecture |
| Primality test | A $n$-digit integer | True or false | Elliptic curve primality proving | $O{\mathord {\left(n^{4+\varepsilon }\right)}}$ heuristically |
| Primality test | A $n$-digit integer | True or false | Baillie–PSW primality test | $O{\mathord {\left(n^{2+\varepsilon }\right)}}$ |
| Primality test | A $n$-digit integer | True or false | Miller–Rabin primality test | $O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ |
| Primality test | A $n$-digit integer | True or false | Solovay–Strassen primality test | $O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ |
| Integer factorization | A $b$-bit input integer | A set of factors | General number field sieve | $O{\mathord {\left((1+\varepsilon )^{b}\right)}}$ |
| Integer factorization | A $b$-bit input integer | A set of factors | Shor's algorithm | $O(M(b)b)$, on a quantum computer |

## 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 or operations on a finite field.
| Operation | Input | Output | Algorithm | Complexity |
| Matrix multiplication | Two $n\times n$ matrices | One $n\times n$ matrix | Schoolbook matrix multiplication | $O(n^{3})$ |
| Matrix multiplication | Two $n\times n$ matrices | One $n\times n$ matrix | Strassen algorithm | $O{\mathord {\left(n^{2.807}\right)}}$ |
| Matrix multiplication | Two $n\times n$ matrices | One $n\times n$ matrix | Coppersmith–Winograd algorithm (galactic algorithm) | $O{\mathord {\left(n^{2.376}\right)}}$ |
| Matrix multiplication | Two $n\times n$ matrices | One $n\times n$ matrix | Optimized CW-like algorithms (galactic algorithms) | $O{\mathord {\left(n^{\psi =2.3728596}\right)}}$ |
| Matrix multiplication | One $n\times m$ matrix, and one $m\times p$ matrix | One $n\times p$ matrix | Schoolbook matrix multiplication | $O(nmp)$ |
| Matrix multiplication | One $n\times \left\lceil n^{k}\right\rceil$ matrix, and one $\left\lceil n^{k}\right\rceil \times n$ matrix, for some $k\geq 0$ | One $n\times n$ matrix | Algorithms given in | $O(n^{\omega (k)+\epsilon })$, where upper bounds on $\omega (k)$ are given in |
| Matrix inversion | One $n\times n$ matrix | One $n\times n$ matrix | Gauss–Jordan elimination | $O{\mathord {\left(n^{3}\right)}}$ |
| Matrix inversion | One $n\times n$ matrix | One $n\times n$ matrix | Strassen algorithm | $O{\mathord {\left(n^{2.807}\right)}}$ |
| Matrix inversion | One $n\times n$ matrix | One $n\times n$ matrix | Coppersmith–Winograd algorithm | $O{\mathord {\left(n^{2.376}\right)}}$ |
| Matrix inversion | One $n\times n$ matrix | One $n\times n$ matrix | Optimized CW-like algorithms | $O{\mathord {\left(n^{\psi }\right)}}$ |
| Singular value decomposition | One $m\times n$ matrix | One $m\times m$ matrix, one $m\times n$ matrix, & one $n\times n$ matrix | Bidiagonalization and QR algorithm | $O{\mathord {\left(m^{2}n\right)}}$ ($m\geq n$) |
| Singular value decomposition | One $m\times n$ matrix | One $m\times n$ matrix, one $n\times n$ matrix, & one $n\times n$ matrix | Bidiagonalization and QR algorithm | $O{\mathord {\left(mn^{2}\right)}}$ ($m\leq n$) |
| QR decomposition | One $m\times n$ matrix | One $m\times n$ matrix, & one $n\times n$ matrix | Algorithms in | $O{\mathord {\left(mn^{1+{\frac {1}{4-\omega }}}\right)}}$ ($m\geq n$) |
| Determinant | One $n\times n$ matrix | One number | Laplace expansion | $O(n!)$ |
| Determinant | One $n\times n$ matrix | One number | Division-free algorithm | $O{\mathord {\left(n^{4}\right)}}$ |
| Determinant | One $n\times n$ matrix | One number | LU decomposition | $O(n^{3})$ |
| Determinant | One $n\times n$ matrix | One number | Bareiss algorithm | $O{\mathord {\left(n^{3}\right)}}$ |
| Determinant | One $n\times n$ matrix | One number | Fast matrix multiplication | $O{\mathord {\left(n^{\psi }\right)}}$ |
| Back substitution | Triangular matrix | $n$ solutions | Back substitution | $O{\mathord {\left(n^{2}\right)}}$ |
| Characteristic polynomial | One $n\times n$ matrix | One degree-$n$ polynomial | Faddeev-LeVerrier algorithm | $O(n^{\psi +1})$ |
| Characteristic polynomial | One $n\times n$ matrix | One degree-$n$ polynomial | Samuelson-Berkowitz algorithm | $O(n^{\psi +1})$ (smaller constant factor) |
| Characteristic polynomial | One $n\times n$ matrix | One degree-$n$ polynomial | Preparata-Sarwate algorithm | $O(n^{\psi +1/2}+n^{3})$ |
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.

## Transforms

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(n^{2})$ |
| Discrete Fourier transform | Finite data sequence of size $n$ | Set of complex numbers | Fast Fourier transform | $O(n\log n)$ |