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 random access machine. See big O notation for an explanation of the notation used.

Arithmetic and algebraic functions

Operation	Input	Output	Algorithm	Complexity
Addition	Two n-digit numbers	One n+1-digit number	Schoolbook addition with carry	O(n)
Subtraction	Two n-digit numbers	One n+1-digit number	Schoolbook subtraction with borrow	O(n)
Multiplication	Two n-digit numbers	One 2n-digit number	Schoolbook long multiplication	O(n2)
			Karatsuba algorithm	O(n1.585)
			3-way Toom–Cook multiplication	O(n1.465)
			k-way Toom–Cook multiplication	$O(n^{1+\epsilon }),\epsilon >0$
			Mixed-level Toom–Cook (Knuth 4.3.3-T)	O(n 2√(2 log n) (log n))
			Schönhage-Strassen algorithm	O(n (log n) (log log n))
			Fürer's algorithm	O(n log n 2log* n)
Note: Due to the variety of multiplication algorithms, M(n) below stands in for the complexity of the chosen multiplication algorithm.
Division	Two n-digit numbers	One n-digit number	Schoolbook long 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	n fixed-size polynomial coefficients	One fixed-size number	Horner's method	O(n)
			Direct evaluation	O(n)

Schnorr and Stumpf conjectured that no fastest algorithm for multiplication exists.

Special functions

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 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	O(n1/2 M(n))
Taylor series; FFT-based acceleration	exp, log, sin, cos	O(n1/3 (log n)2 M(n))
Taylor series; binary splitting	exp, log, sin, cos	O((log n)2 M(n))
Arithmetic-geometric mean iteration	log	O((log n) M(n))

It is not known whether O((log n) M(n)) is the optimal complexity for elementary functions. The best known lower bound is the trivial bound O(M(n)).

Non-elementary functions

Function	Input	Algorithm	Complexity
Gamma function	n-digit number	Series approximation of the incomplete gamma function	O(n1/2 (log n)2 M(n))
	Fixed rational number	Hypergeometric series	O((log n)2 M(n))
	m/24, m an integer	Arithmetic-geometric mean iteration	O((log n) M(n))
Hypergeometric function pFq	n-digit number	(As described in Borwein & Borwein)	O(n1/2 (log n)2 M(n))
	Fixed rational number	Hypergeometric series	O((log n)2 M(n))

Mathematical constants

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

Constant	Algorithm	Complexity
Golden ratio, φ	Newton's method	O(M(n))
Square root of 2, √2	Newton's method	O(M(n))
Euler's number, e	Binary splitting of the Taylor series for the exponential function	O((log n) M(n))
	Newton inversion of the natural logarithm	O((log n) M(n))
Pi, π	Binary splitting of the arctan series in Machin's formula	O((log n)2 M(n))
	Brent-Salamin algorithm	O((log n) M(n))
Euler's constant, γ	Sweeney's method (approximation in terms of the exponential integral)	O((log n)2 M(n))

Number theory

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

Operation	Input	Output	Algorithm	Complexity
Greatest common divisor	Two n-digit numbers	One number with at most n digits	Euclidean algorithm	O(n2)
			Binary GCD algorithm	O(n2)
			Stehlé-Zimmermann algorithm	O((log n) M(n))
			Schönhage Controlled Euclidean Descent algorithm	O((log n) M(n))
Factorial	A fixed-size number m	One O((m+1/2)(log m) - m)-digit number	Bottom-up multiplication	O(m2 log m)
			Binary splitting	O((log m) M(m log m))
			Exponentiation of the prime factors of m	O((log log m) M(m log m)), O(M(m log m))

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 multiplication	One n×m-matrix & One m×p-matrix	One n×p-matrix	Schoolbook matrix multiplication	O(nmp)
Matrix inversion	One n×n-matrix	One n×n-matrix	Gaussian elimination	O(n3)
			Strassen algorithm	O(n2.807)
			Coppersmith–Winograd algorithm	O(n2.376)

In 2005,Henry Cohn, Robert Kleinberg, Balázs Szegedy and Christopher Umans showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2. It has also been conjectured that no fastest algorithm for matrix multiplication exists, in light of the nearly 20 successive improvements leading to the Coppersmith-Winograd algorithm.