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, 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 -digit numbers	One -digit number	Schoolbook addition with carry
Subtraction	Two -digit numbers	One -digit number	Schoolbook subtraction with borrow
Multiplication	Two -digit numbers	One -digit number	Schoolbook long multiplication
Multiplication	Two -digit numbers	One -digit number	Karatsuba algorithm
Multiplication	Two -digit numbers	One -digit number	3-way Toom–Cook multiplication
Multiplication	Two -digit numbers	One -digit number		-
Multiplication	Two -digit numbers	One -digit number	Mixed-level Toom–Cook
Multiplication	Two -digit numbers	One -digit number	Schönhage–Strassen algorithm
Multiplication	Two -digit numbers	One -digit number	Harvey-Hoeven algorithm
Division	Two -digit numbers	One -digit number	Schoolbook long division
Division	Two -digit numbers	One -digit number	Burnikel–Ziegler Divide-and-Conquer Division
Division	Two -digit numbers	One -digit number	Newton–Raphson division
Square root	One -digit number	One -digit number	Newton's method
Modular exponentiation	Two -digit integers and a -bit exponent	One -digit integer	Repeated multiplication and reduction
Modular exponentiation	Two -digit integers and a -bit exponent	One -digit integer	Exponentiation by squaring
Modular exponentiation	Two -digit integers and a -bit exponent	One -digit integer	Exponentiation with Montgomery reduction

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.

Algebraic functions

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. For this section indicates the time needed for multiplying two polynomials of degree at most.

Operation	Input	Output	Algorithm	Complexity
Polynomial evaluation	One polynomial of degree with integer coefficients	One number	Direct evaluation
Polynomial evaluation	One polynomial of degree with integer coefficients	One number	Horner's method
Polynomial multipoint evaluation	One polynomial of degree less than with integer coefficients and numbers as evaluation points	numbers	Direct evaluation
Polynomial multipoint evaluation	One polynomial of degree less than with integer coefficients and numbers as evaluation points	numbers	Fast multipoint evaluation
Polynomial gcd	Two polynomials of degree with integer coefficients	One polynomial of degree at most	Euclidean algorithm
Polynomial gcd	Two polynomials of degree with integer coefficients	One polynomial of degree at most	Fast Euclidean algorithm

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, the natural logarithm, trigonometric functions, 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 or in the complex domain can be computed with some complexity, then that complexity is attainable for all other elementary functions.
Below, the size refers to the number of digits of precision at which the function is to be evaluated.

Algorithm	Applicability	Complexity
Taylor series; repeated argument reduction and direct summation
Taylor series; FFT-based acceleration
Taylor series; binary splitting + bit-burst algorithm
Arithmetic–geometric mean iteration

It is not known whether is the optimal complexity for elementary functions. The best known lower bound is the trivial bound

Mathematical constants

This table gives the complexity of computing approximations to the given constants to correct digits.

Constant	Algorithm	Complexity
Golden ratio,	Newton's method
Square root of 2,	Newton's method
Euler's number,	Binary splitting of the Taylor series for the exponential function
Euler's number,	Newton inversion of the natural logarithm
Pi,	Binary splitting of the arctan series in Machin's formula
Pi,	Gauss–Legendre algorithm
Euler's constant,	Sweeney's method

Number theory

Algorithms for number theoretical calculations are studied in computational number theory.

Operation	Input	Output	Algorithm	Complexity
Greatest common divisor	Two -digit integers	One integer with at most digits	Euclidean algorithm
Greatest common divisor	Two -digit integers	One integer with at most digits	Binary GCD algorithm
Greatest common divisor	Two -digit integers	One integer with at most digits	Left/right k-ary binary GCD algorithm
Greatest common divisor	Two -digit integers	One integer with at most digits	Stehlé–Zimmermann algorithm
Greatest common divisor	Two -digit integers	One integer with at most digits	Schönhage controlled Euclidean descent algorithm
Jacobi symbol	Two -digit integers	, or	Schönhage controlled Euclidean descent algorithm
Jacobi symbol	Two -digit integers	, or	Stehlé–Zimmermann algorithm
Factorial	A positive integer less than	One -digit integer	Bottom-up multiplication
Factorial	A positive integer less than	One -digit integer	Binary splitting
Factorial	A positive integer less than	One -digit integer	Exponentiation of the prime factors of	,
Primality test	A -digit integer	True or false	AKS primality test	, assuming Agrawal's conjecture
Primality test	A -digit integer	True or false	Elliptic curve primality proving	heuristically
Primality test	A -digit integer	True or false	Baillie–PSW primality test
Primality test	A -digit integer	True or false	Miller–Rabin primality test
Primality test	A -digit integer	True or false	Solovay–Strassen primality test
Integer factorization	A -bit input integer	A set of factors	General number field sieve
Integer factorization	A -bit input integer	A set of factors	Shor's algorithm	, on a quantum computer

Matrix algebra

The following complexity figures assume that arithmetic with individual elements has complexity O, as is the case with fixed-precision floating-point arithmetic or operations on a finite field.

Operation	Input	Output	Algorithm	Complexity
Matrix multiplication	Two matrices	One matrix	Schoolbook matrix multiplication
Matrix multiplication	Two matrices	One matrix	Strassen algorithm
Matrix multiplication	Two matrices	One matrix	Coppersmith–Winograd algorithm
Matrix multiplication	Two matrices	One matrix	Optimized CW-like algorithms
Matrix multiplication	One matrix, and one matrix	One matrix	Schoolbook matrix multiplication
Matrix multiplication	One matrix, and one matrix, for some	One matrix	Algorithms given in	, where upper bounds on are given in
Matrix inversion	One matrix	One matrix	Gauss–Jordan elimination
Matrix inversion	One matrix	One matrix	Strassen algorithm
Matrix inversion	One matrix	One matrix	Coppersmith–Winograd algorithm
Matrix inversion	One matrix	One matrix	Optimized CW-like algorithms
Singular value decomposition	One matrix	One matrix, one matrix, & one matrix	Bidiagonalization and QR algorithm
Singular value decomposition	One matrix	One matrix, one matrix, & one matrix	Bidiagonalization and QR algorithm
QR decomposition	One matrix	One matrix, & one matrix	Algorithms in
Determinant	One matrix	One number	Laplace expansion
Determinant	One matrix	One number	Division-free algorithm
Determinant	One matrix	One number	LU decomposition
Determinant	One matrix	One number	Bareiss algorithm
Determinant	One matrix	One number	Fast matrix multiplication
Back substitution	Triangular matrix	solutions	Back substitution
Characteristic polynomial	One matrix	One degree- polynomial	Faddeev-LeVerrier algorithm
Characteristic polynomial	One matrix	One degree- polynomial	Samuelson-Berkowitz algorithm
Characteristic polynomial	One matrix	One degree- polynomial	Preparata-Sarwate algorithm

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 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	Set of complex numbers	Schoolbook
Discrete Fourier transform	Finite data sequence of size	Set of complex numbers	Fast Fourier transform