Movatterモバイル変換

[0]ホーム

Jump to content

Computational complexity of mathematical operations

Edit links

From Wikipedia, the free encyclopedia

Algorithmic runtime requirements for common math procedures

This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Computational complexity of mathematical operations" – news ·newspapers ·books ·scholar ·JSTOR(April 2015) (Learn how and when to remove this message)

This article needs editing tocomply with Wikipedia'sManual of Style. In particular, it has problems withMOS:FORMULA - avoid mixing<math>...</math> and{{math}} in the same expression. Please helpimprove the content.(July 2025) (Learn how and when to remove this message)

Graphs of functions commonly used in the analysis of algorithms, showing the number of operations $N {\displaystyle N}$ versus input size $n {\displaystyle n}$ for each function

Graphs of functions commonly used in the analysis of algorithms, showing the number of operations $N {\displaystyle N}$ versus input size $n {\displaystyle n}$ for each function

The following tables list thecomputational complexity of variousalgorithms for commonmathematical operations.

Here, complexity refers to thetime complexity of performing computations on amultitape Turing machine.^[1] Seebig 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

[edit]

This table lists the complexity of mathematical operations on integers.

Operation	Input	Output	Algorithm	Complexity
Addition	Two $n {\displaystyle n}$ -digit numbers	One $n+1$ -digit number	Schoolbook addition with carry	$\Theta (n)$
Subtraction	Two $n {\displaystyle n}$ -digit numbers	One $n {\displaystyle n}$ -digit number	Schoolbook subtraction with borrow	$\Theta (n)$
Multiplication	Two $n {\displaystyle n}$ -digit numbers	One $2n$ -digit number	Schoolbook long multiplication	$O{\mathord {\left(n^{2}\right)}}$
			Karatsuba algorithm	$O{\mathord {\left(n^{1.585}\right)}}$
			3-wayToom–Cook multiplication	$O{\mathord {\left(n^{1.465}\right)}}$
			$k {\displaystyle k}$ -way Toom–Cook multiplication	$O{\mathord {\left(n^{\frac {\log(2k-1)}{\log k}}\right)}}$
			Mixed-level Toom–Cook (Knuth 4.3.3-T)^[2]	$O{\mathord {\left(n\,2^{\sqrt {2\log n}}\,\log n\right)}}$
			Schönhage–Strassen algorithm	$O{\mathord {\left(n\log n\log \log n\right)}}$
			Harvey-Hoeven algorithm^[3]^[4]	$O(n\log n)$
Division	Two $n {\displaystyle n}$ -digit numbers	One $n {\displaystyle n}$ -digit number	Schoolbook long division	$O{\mathord {\left(n^{2}\right)}}$
			Burnikel–Ziegler Divide-and-Conquer Division^[5]	$O(M(n)\log n)$
			Newton–Raphson division	$O(M(n))$
Square root	One $n {\displaystyle n}$ -digit number	One $n/2$ -digit number	Newton's method	$O(M(n))$
Modular exponentiation	Two $n {\displaystyle n}$ -digit integers and a $k {\displaystyle k}$ -bit exponent	One $n {\displaystyle n}$ -digit integer	Repeated multiplication and reduction	$O{\mathord {\left(M(n)\,2^{k}\right)}}$
			Exponentiation by squaring	$O(M(n)\,k)$
			Exponentiation withMontgomery reduction	$O(M(n)\,k)$

On stronger computational models, specifically apointer machine and consequently also aunit-cost random-access machine it is possible to multiply twon-bit numbers in timeO(n).^[6]

Algebraic functions

[edit]

Here we consider operations over polynomials andn denotes their degree; for the coefficients we use aunit-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 $M(n)$ indicates the time needed for multiplying two polynomials of degree at most $n {\displaystyle n}$ .^[7]^: 242

Operation	Input	Output	Algorithm	Complexity
Polynomial evaluation	One polynomial of degree $n {\displaystyle n}$ with integer coefficients	One number	Direct evaluation	$\Theta (n)$
Polynomial evaluation		One number	Horner's method	$\Theta (n)$
Polynomial multipoint evaluation	One polynomial of degree less than $n {\displaystyle n}$ with integer coefficients and $n {\displaystyle n}$ numbers as evaluation points	$n {\displaystyle n}$ numbers	Direct evaluation	$\Theta (n^{2})$
Polynomial multipoint evaluation		$n {\displaystyle n}$ numbers	Fast multipoint evaluation^[7]^: 295	$O(M(n)\log n)$
Polynomial gcd (over $\mathbb {Z} [x]$ or $F[x]$ )	Two polynomials of degree $n {\displaystyle n}$ with integer coefficients	One polynomial of degree at most $n {\displaystyle n}$	Euclidean algorithm	$O{\mathord {\left(n^{2}\right)}}$
Polynomial gcd (over $\mathbb {Z} [x]$ or $F[x]$ )		One polynomial of degree at most $n {\displaystyle n}$	Fast Euclidean algorithm^[7]^: 318 (Lehmer^[7]^: 324)	$O(M(n)\log n)$

Special functions

[edit]

Many of the methods in this section are given in Borwein & Borwein.^[8]

Elementary functions

[edit]

Theelementary functions are constructed by composing arithmetic operations, theexponential function ( $\exp$ ), thenatural 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 areanalytic 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 {\displaystyle 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^[9]	$\exp ,\log ,\sin ,\cos ,\arctan$	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$
Arithmetic–geometric mean iteration^[10]	$\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

[edit]

Function	Input	Algorithm	Complexity
Gamma function	Integer $n {\displaystyle n}$	Series approximation of theincomplete gamma function	$O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}$
	Fixed rational number	Hypergeometric series	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$
	$m/24$ , for $m {\displaystyle m}$ integer.	Arithmetic-geometric mean iteration	$O(M(n)\log n)$
Hypergeometric function ${}_{p}\!F_{q}$	$n {\displaystyle 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

[edit]

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

Number theory

[edit]

Algorithms fornumber theoretical calculations are studied incomputational number theory.

Operation	Input	Output	Algorithm	Complexity
Greatest common divisor	Two $n {\displaystyle n}$ -digit integers	One integer with at most $n {\displaystyle n}$ digits	Euclidean algorithm	$O{\mathord {\left(n^{2}\right)}}$
			Binary GCD algorithm	$O{\mathord {\left(n^{2}\right)}}$
			Left/rightk-ary binary GCD algorithm^[12]	$O{\mathord {\left({\frac {n^{2}}{\log n}}\right)}}$
			Stehlé–Zimmermann algorithm^[13]	$O(M(n)\log n)$
			Schönhage controlled Euclidean descent algorithm^[14]	$O(M(n)\log n)$
Jacobi symbol	Two $n {\displaystyle n}$ -digit integers	$0 {\displaystyle 0}$ , $-1$ or $1 {\displaystyle 1}$	Schönhage controlled Euclidean descent algorithm^[15]	$O(M(n)\log n)$
Jacobi symbol	Two $n {\displaystyle n}$ -digit integers	$0 {\displaystyle 0}$ , $-1$ or $1 {\displaystyle 1}$	Stehlé–Zimmermann algorithm^[16]	$O(M(n)\log n)$
Factorial	A positive integer less than $m {\displaystyle m}$	One $O(m\log m)$ -digit integer	Bottom-up multiplication	$O{\mathord {\left(M\left(m^{2}\right)\log m\right)}}$
			Binary splitting	$O(M(m\log m)\log m)$
			Exponentiation of the prime factors of $m {\displaystyle m}$	$O(M(m\log m)\log \log m)$ ,^[17] $O(M(m\log m))$ ^[1]
Primality test	A $n {\displaystyle n}$ -digit integer	True or false	AKS primality test	$O{\mathord {\left(n^{6+o(1)}\right)}}$ ^[18]^[19] $O(n^{3})$ , assumingAgrawal's conjecture
			Elliptic curve primality proving	$O{\mathord {\left(n^{4+\varepsilon }\right)}}$ heuristically^[20]
			Baillie–PSW primality test	$O{\mathord {\left(n^{2+\varepsilon }\right)}}$ ^[21]^[22]
			Miller–Rabin primality test	$O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ ^[23]
			Solovay–Strassen primality test	$O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ ^[23]
Integer factorization	A $b {\displaystyle b}$ -bit input integer	A set of factors	General number field sieve	$O{\mathord {\left((1+\varepsilon )^{b}\right)}}$ ^{[nb 1]}
Integer factorization	A $b {\displaystyle b}$ -bit input integer	A set of factors	Shor's algorithm	$O(M(b)b)$ , on aquantum computer

Matrix algebra

[edit]

Main article:Computational complexity of matrix multiplication

The following complexity figures assume that arithmetic with individual elements has complexityO(1), as is the case with fixed-precisionfloating-point arithmetic or operations on afinite field.

Operation	Input	Output	Algorithm	Complexity
Matrix multiplication	Two $n\times n$ matrices	One $n\times n$ matrix	Schoolbook matrix multiplication	$O(n^{3})$
			Strassen algorithm	$O{\mathord {\left(n^{2.807}\right)}}$
			Coppersmith–Winograd algorithm (galactic algorithm)	$O{\mathord {\left(n^{2.376}\right)}}$
			Optimized CW-like algorithms^[24]^[25]^[26]^[27] (galactic algorithms)	$O{\mathord {\left(n^{\psi =2.3728596}\right)}}$
	One $n\times m$ matrix, and one $m\times p$ matrix	One $n\times p$ matrix	Schoolbook matrix multiplication	$O(nmp)$
	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^[28]	$O(n^{\omega (k)+\epsilon })$ , where upper bounds on $\omega (k)$ are given in^[28]
Matrix inversion	One $n\times n$ matrix	One $n\times n$ matrix	Gauss–Jordan elimination	$O{\mathord {\left(n^{3}\right)}}$
			Strassen algorithm	$O{\mathord {\left(n^{2.807}\right)}}$
			Coppersmith–Winograd algorithm	$O{\mathord {\left(n^{2.376}\right)}}$
			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^[29]	$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!)$
			Division-free algorithm^[30]	$O{\mathord {\left(n^{4}\right)}}$ $O{\mathord {\left(n^{2.697263}\right)}}$ ^[31]
			LU decomposition	$O(n^{3})$
			Bareiss algorithm	$O{\mathord {\left(n^{3}\right)}}$
			Fast matrix multiplication^[32]	$O{\mathord {\left(n^{\psi }\right)}}$
Back substitution	Triangular matrix	$n {\displaystyle n}$ solutions	Back substitution^[33]	$O{\mathord {\left(n^{2}\right)}}$
Characteristic polynomial	One $n\times n$ matrix	One degree- $n {\displaystyle n}$ polynomial	Faddeev-LeVerrier algorithm	$O(n^{\psi +1})$
			Samuelson-Berkowitz algorithm	$O(n^{\psi +1})$ (smaller constant factor)
			Preparata-Sarwate algorithm^[34]^[35]	$O(n^{\psi +1/2}+n^{3})$

In 2005,Henry Cohn,Robert Kleinberg,Balázs Szegedy, andChris Umans showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2.^[36]

Transforms

[edit]

Algorithms for computingtransforms of functions (particularlyintegral transforms) are widely used in all areas of mathematics, particularlyanalysis andsignal processing.

Operation	Input	Output	Algorithm	Complexity
Discrete Fourier transform	Finite data sequence of size $n {\displaystyle n}$	Set of complex numbers	Schoolbook	$O(n^{2})$
Discrete Fourier transform	Finite data sequence of size $n {\displaystyle n}$	Set of complex numbers	Fast Fourier transform	$O(n\log n)$