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.

OperationInputOutputAlgorithmComplexity AdditionTwo -digit numbersOne -digit numberSchoolbook addition with carrySubtractionTwo -digit numbersOne -digit numberSchoolbook subtraction with borrowMultiplicationTwo -digit numbersOne -digit numberSchoolbook long multiplicationKaratsuba algorithm3-way Toom–Cook multiplication-way Toom–Cook multiplicationMixed-level Toom–Cook (Knuth 4.3.3-T)Schönhage–Strassen algorithmHarvey-Hoeven algorithmDivisionTwo -digit numbersOne -digit numberSchoolbook long divisionBurnikel–Ziegler Divide-and-Conquer DivisionNewton–Raphson divisionSquare rootOne -digit numberOne -digit numberNewton's methodModular exponentiationTwo -digit integers and a -bit exponentOne -digit integerRepeated multiplication and reductionExponentiation by squaringExponentiation 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(n).

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 . OperationInputOutputAlgorithmComplexityPolynomial evaluation One polynomial of degree with integer coefficients One numberDirect evaluationHorner's methodPolynomial multipoint evaluation One polynomial of degree less than with integer coefficients and numbers as evaluation points numbersDirect evaluationFast multipoint evaluationPolynomial gcd (over or ) Two polynomials of degree with integer coefficients One polynomial of degree at most Euclidean algorithmFast Euclidean algorithm (Lehmer)

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.

AlgorithmApplicabilityComplexityTaylor series; repeated argument reduction (e.g. ) and direct summationTaylor series; FFT-based accelerationTaylor series; binary splitting + bit-burst algorithmArithmetic–geometric mean iteration

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

Non-elementary functions FunctionInputAlgorithmComplexityGamma functionInteger Series approximation of the incomplete gamma functionFixed rational numberHypergeometric series, for integer.Arithmetic-geometric mean iterationHypergeometric function -digit number(As described in Borwein & Borwein)Fixed rational numberHypergeometric series

Mathematical constants This table gives the complexity of computing approximations to the given constants to correct digits. ConstantAlgorithmComplexityGolden ratio, Newton's methodSquare root of 2, Newton's methodEuler's number, Binary splitting of the Taylor series for the exponential functionNewton inversion of the natural logarithmPi, Binary splitting of the arctan series in Machin's formulaGauss–Legendre algorithmEuler's constant, Sweeney's method (approximation in terms of the exponential integral)

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

OperationInputOutputAlgorithmComplexityGreatest common divisorTwo -digit integersOne integer with at most digitsEuclidean algorithmBinary GCD algorithmLeft/right k-ary binary GCD algorithmStehlé–Zimmermann algorithmSchönhage controlled Euclidean descent algorithmJacobi symbolTwo -digit integers, or Schönhage controlled Euclidean descent algorithmStehlé–Zimmermann algorithmFactorialA positive integer less than One -digit integerBottom-up multiplicationBinary splittingExponentiation of the prime factors of ,Primality testA -digit integerTrue or falseAKS primality test, assuming Agrawal's conjectureElliptic curve primality proving heuristicallyBaillie–PSW primality testMiller–Rabin primality testSolovay–Strassen primality testInteger factorizationA -bit input integerA set of factorsGeneral number field sieveThis form of sub-exponential time is valid for all . A more precise form of the complexity can be given as Shor's algorithm, 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.

OperationInputOutputAlgorithmComplexityMatrix multiplicationTwo matricesOne matrixSchoolbook matrix multiplicationStrassen algorithmCoppersmith–Winograd algorithm (galactic algorithm)Optimized CW-like algorithms (galactic algorithms)One matrix, and one matrixOne matrixSchoolbook matrix multiplicationOne matrix, and one matrix, for some One matrixAlgorithms given in , where upper bounds on are given in Matrix inversionOne matrixOne matrixGauss–Jordan eliminationStrassen algorithmCoppersmith–Winograd algorithmFast matrix multiplication algorithms for , Sect. 11, pp. 413-414 .Singular value decompositionOne matrixOne matrix, one matrix, & one matrix Bidiagonalization and QR algorithm ()One matrix, one matrix, & one matrix Bidiagonalization and QR algorithm ()QR decompositionOne matrixOne matrix, & one matrix Algorithms in by fast matrix multiplication ()DeterminantOne matrixOne numberLaplace expansionDivision-free algorithmLU decompositionBareiss algorithmFast matrix multiplicationBack substitutionTriangular matrix solutionsBack substitutionCharacteristic polynomialOne matrixOne degree- polynomialFaddeev-LeVerrier algorithmSamuelson-Berkowitz algorithm (smaller constant factor)Preparata-Sarwate algorithm, in which the term is reducedBy fast matrix multiplication

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. OperationInputOutputAlgorithmComplexityDiscrete Fourier transformFinite data sequence of size Set of complex numbersSchoolbookFast Fourier transform

Notes

References

Further reading