Computational complexity of mathematical operations explained

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.[1] 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.

OperationInputOutputAlgorithmComplexity
AdditionTwo

n

-digit numbers
One

n+1

-digit number
Schoolbook addition with carry

\Theta(n)

SubtractionTwo

n

-digit numbers
One

n+1

-digit number
Schoolbook subtraction with borrow

\Theta(n)

MultiplicationTwo

n

-digit numbers
One

2n

-digit number
Schoolbook long multiplication

Od\left(n2\right)

Karatsuba algorithm

Od\left(n1.585\right)

3-way Toom–Cook multiplication

Od\left(n1.465\right)

k

-way Toom–Cook multiplication
log(2k-1)
logk
Od\left(n

\right)

Mixed-level Toom–Cook (Knuth 4.3.3-T)

Od\left(n2\sqrt{2

} \, \log n\right)
Schönhage–Strassen algorithm

Od\left(nlognloglogn\right)

Harvey-Hoeven algorithm[2] [3]

O(nlogn)

DivisionTwo

n

-digit numbers
One

n

-digit number
Schoolbook long division

Od\left(n2\right)

Burnikel–Ziegler Divide-and-Conquer Division[4]

O(M(n)logn)

Newton–Raphson division

O(M(n))

Square rootOne

n

-digit number
One

n

-digit number
Newton's method

O(M(n))

Modular exponentiationTwo

n

-digit integers and a

k

-bit exponent
One

n

-digit integer
Repeated multiplication and reduction

Od\left(M(n)2k\right)

Exponentiation by squaring

O(M(n)k)

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 -bit numbers in time O(n).[5]

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.

OperationInputOutputAlgorithmComplexity
Polynomial evaluationOne polynomial of degree

n

with integer coefficients
One numberDirect evaluation

\Theta(n)

Horner's method

\Theta(n)

Polynomial gcd (over

Z[x]

or

F[x]

)
Two polynomials of degree

n

with integer coefficients
One polynomial of degree at most

n

Euclidean algorithm

Od\left(n2\right)

Fast Euclidean algorithm (Lehmer)

O(M(n)logn)

Special functions

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

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.
AlgorithmApplicabilityComplexity
Taylor series
repeated argument reduction (e.g.

\exp(2x)=[\exp(x)]2

) and direct summation

\exp,log,\sin,\cos,\arctan

Od\left(M(n)n1/2\right)

Taylor series; FFT-based acceleration

\exp,log,\sin,\cos,\arctan

Od\left(M(n)n1/3(logn)2\right)

Taylor series; binary splitting + bit-burst algorithm[7]

\exp,log,\sin,\cos,\arctan

Od\left(M(n)(logn)2\right)

Arithmetic–geometric mean iteration[8]

\exp,log,\sin,\cos,\arctan

O(M(n)logn)

It is not known whether

O(M(n)logn)

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

(M(n))

.

Non-elementary functions

FunctionInputAlgorithmComplexity
Gamma function

n

-digit number
Series approximation of the incomplete gamma function

Od\left(M(n)n1/2(logn)2\right)

Fixed rational numberHypergeometric series

Od\left(M(n)(logn)2\right)

m/24

, for

m

integer.
Arithmetic-geometric mean iteration

O(M(n)logn)

Hypergeometric function

{}p\

F_q

n

-digit number
(As described in Borwein & Borwein)

Od\left(M(n)n1/2(logn)2\right)

Fixed rational numberHypergeometric series

Od\left(M(n)(logn)2\right)

Mathematical constants

This table gives the complexity of computing approximations to the given constants to

n

correct digits.
ConstantAlgorithmComplexity
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)logn)

Newton inversion of the natural logarithm

O(M(n)logn)

Pi,

\pi

Binary splitting of the arctan series in Machin's formula

Od\left(M(n)(logn)2\right)

Gauss–Legendre algorithm

O(M(n)logn)

Euler's constant,

\gamma

Sweeney's method (approximation in terms of the exponential integral)

Od\left(M(n)(logn)2\right)

Number theory

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

OperationInputOutputAlgorithmComplexity
Greatest common divisorTwo

n

-digit integers
One integer with at most

n

digits
Euclidean algorithm

Od\left(n2\right)

Binary GCD algorithm

Od\left(n2\right)

Left/right k-ary binary GCD algorithm[9]
O
d\left(n2
logn
\right)
Stehlé–Zimmermann algorithm[10]

O(M(n)logn)

Schönhage controlled Euclidean descent algorithm[11]

O(M(n)logn)

Jacobi symbolTwo

n

-digit integers

0

,

-1

or

1

Schönhage controlled Euclidean descent algorithm[12]

O(M(n)logn)

Stehlé–Zimmermann algorithm[13]

O(M(n)logn)

FactorialA positive integer less than

m

One

O(mlogm)

-digit integer
Bottom-up multiplication

Od\left(M\left(m2\right)logm\right)

Binary splitting

O(M(mlogm)logm)

Exponentiation of the prime factors of

m

O(M(mlogm)loglogm)

,[14]

O(M(mlogm))

Primality testA

n

-digit integer
True or falseAKS primality test

Od\left(n6+o(1)\right)

[15] [16]

O(n3)

, assuming Agrawal's conjecture
Elliptic curve primality proving

Od\left(n4+\varepsilon\right)

heuristically[17]
Baillie–PSW primality test

Od\left(n2+\varepsilon\right)

[18] [19]
Miller–Rabin primality test

Od\left(kn2+\varepsilon\right)

[20]
Solovay–Strassen primality test

Od\left(kn2+\varepsilon\right)

Integer factorizationA

b

-bit input integer
A set of factorsGeneral number field sieve

Od\left((1+\varepsilon)b\right)

[21]
Shor's algorithm

O(M(b)b)

, on a quantum computer

Matrix algebra

See main article: Computational complexity of matrix multiplication. 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.

OperationInputOutputAlgorithmComplexity
Matrix multiplicationTwo

n x n

matrices
One

n x n

matrix
Schoolbook matrix multiplication

O(n3)

Strassen algorithm

Od\left(n2.807\right)

Coppersmith–Winograd algorithm (galactic algorithm)

Od\left(n2.376\right)

Optimized CW-like algorithms (galactic algorithms)

Od\left(n\psi=2.3728596\right)

Matrix multiplicationOne

n x m

matrix, and
one

m x p

matrix
One

n x p

matrix
Schoolbook matrix multiplication

O(nmp)

Matrix multiplicationOne

n x \left\lceilnk\right\rceil

matrix, and
one

\left\lceilnk\right\rceil x n

matrix, for some

k\geq0

One

n x n

matrix
Algorithms given in [22]

O(n\omega(k)+\epsilon)

, where upper bounds on

\omega(k)

are given in
Matrix inversionOne

n x n

matrix
One

n x n

matrix
Gauss–Jordan elimination

Od\left(n3\right)

Strassen algorithm

Od\left(n2.807\right)

Coppersmith–Winograd algorithm

Od\left(n2.376\right)

Optimized CW-like algorithms

Od\left(n\psi\right)

Singular value decompositionOne

m x n

matrix
One

m x m

matrix,
one

m x n

matrix, &
one

n x n

matrix
Bidiagonalization and QR algorithm

Od\left(m2n\right)


(

m\geqn

)
One

m x n

matrix,
one

n x n

matrix, &
one

n x n

matrix
Bidiagonalization and QR algorithm

Od\left(mn2\right)


(

m\leqn

)
QR decompositionOne

m x n

matrix
One

m x n

matrix, &
one

n x n

matrix
Algorithms in [23]
1+1
4-\omega
Od\left(mn

\right)


(

m\geqn

)
DeterminantOne

n x n

matrix
One numberLaplace expansion

O(n!)

Division-free algorithm[24]

Od\left(n4\right)

LU decomposition

O(n3)

Bareiss algorithm

Od\left(n3\right)

Fast matrix multiplication[25]

Od\left(n\psi\right)

Back substitutionTriangular matrix

n

solutions
Back substitution[26]

Od\left(n2\right)

Characteristic polynomialOne

n x n

matrix
One degree-

n

polynomial
Faddeev-LeVerrier algorithm

O(n\psi+1)

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.[27]

Transforms

Algorithms for computing transforms of functions (particularly integral transforms) are widely used in all areas of mathematics, particularly analysis and signal processing.

OperationInputOutputAlgorithmComplexity
Discrete Fourier transformFinite data sequence of size

n

Set of complex numbersSchoolbook

O(n2)

Fast Fourier transform

O(nlogn)

Further reading

Notes and References

  1. Book: A. . Schönhage . A.F.W. . Grotefeld . E. . Vetter . Fast Algorithms—A Multitape Turing Machine Implementation . BI Wissenschafts-Verlag . 1994 . 978-3-411-16891-0 . 897602049.
  2. Harvey . D. . Van Der Hoeven . J. . Integer multiplication in time O (n log n) . Annals of Mathematics . 193 . 2 . 563–617 . 2021 . 10.4007/annals.2021.193.2.4 . 109934776 .
  3. Erica . Klarreich . Multiplication hits the speed limit . Commun. ACM . 63 . 1 . 11–13 . December 2019 . 10.1145/3371387 . 209450552 .
  4. Book: Burnikel . Christoph . Joachim . Ziegler . Fast Recursive Division . MPI Informatik Bibliothek & Dokumentation . Forschungsberichte des Max-Planck-Instituts für Informatik . 1998 . MPII-98-1-022 . Saarbrücken . 246319574.
  5. Schönhage . Arnold . Storage Modification Machines . SIAM Journal on Computing . 1980 . 9 . 3 . 490–508 . 10.1137/0209036.
  6. Book: J. . Borwein . P. . Borwein . Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity . Wiley . 1987 . 978-0-471-83138-9 . 755165897.
  7. Book: David . Chudnovsky . Gregory . Chudnovsky . Approximations and complex multiplication according to Ramanujan . Ramanujan revisited: Proceedings of the Centenary Conference . Academic Press . 1988 . 978-0-01-205856-5 . 375–472 .
  8. Book: Brent, Richard P. . 1004.3412 . Multiple-precision zero-finding methods and the complexity of elementary function evaluation . . J.F. . Traub . Analytic Computational Complexity . Elsevier . 2014 . 1975 . 978-1-4832-5789-1 . 151–176 .
  9. J. . Sorenson . Two Fast GCD Algorithms . Journal of Algorithms . 16 . 1. 110–144 . 1994 . 10.1006/jagm.1994.1006.
  10. Book: R. . Crandall . C. . Pomerance . Algorithm 9.4.7 (Stehlé-Zimmerman binary-recursive-gcd) . . 471–3 . Prime Numbers – A Computational Perspective . Springer . 2nd . 2005 . 978-0-387-28979-3.
  11. Möller N . On Schönhage's algorithm and subquadratic integer gcd computation . Mathematics of Computation . 77 . 261 . 589–607 . 10.1090/S0025-5718-07-02017-0 . 2008 . 2008MaCom..77..589M . free .
  12. Web site: Faster Algorithms to Find Non-squares Modulo Worst-case Integers. Bernstein . D.J..
  13. Book: 1004.2091 . Richard P. . Brent . Paul . Zimmermann . An

    O(M(n)logn)

    algorithm for the Jacobi symbol. 2010 . International Algorithmic Number Theory Symposium . 83–95 . Springer . 10.1007/978-3-642-14518-6_10 . https://link.springer.com/chapter/10.1007/978-3-642-14518-6_10 . 978-3-642-14518-6. 7632655 .
  14. Borwein . P. . 1985 . On the complexity of calculating factorials . Journal of Algorithms . 6 . 3. 376–380 . 10.1016/0196-6774(85)90006-9.
  15. H.W. . Lenstra jr. . Carl . Pomerance . Hendrik Lenstra . Carl Pomerance . Primality testing with Gaussian periods . . 2019 . 21 . 4 . 1229–69 . 10.4171/JEMS/861 . 21.11116/0000-0005-717D-0 .
  16. Book: Tao, Terence. An epsilon of room, II: Pages from year three of a mathematical blog. American Mathematical Society. 2010. 978-0-8218-5280-4. Graduate Studies in Mathematics. 117 . 82–86. 1.11 The AKS primality test. 10.1090/gsm/117. 2780010. Terence Tao. https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/.
  17. Morain. F.. 2007. Implementing the asymptotically fast version of the elliptic curve primality proving algorithm. Mathematics of Computation. 76. 257. 493–505. math/0502097. 2007MaCom..76..493M. 10.1090/S0025-5718-06-01890-4. 2261033. 133193.
  18. Carl . Pomerance. John L. . Selfridge. John L. Selfridge. Samuel S. . Wagstaff, Jr.. Samuel S. Wagstaff, Jr.. July 1980. [//math.dartmouth.edu/~carlp/PDF/paper25.pdf The pseudoprimes to 25·10<sup>9</sup>]. Mathematics of Computation. 35. 151. 1003–26. 10.1090/S0025-5718-1980-0572872-7. 2006210. Carl Pomerance. free.
  19. Robert . Baillie. Samuel S. . Wagstaff, Jr.. Samuel S. Wagstaff, Jr.. October 1980. Lucas Pseudoprimes. Mathematics of Computation. 35. 152. 1391–1417. 10.1090/S0025-5718-1980-0583518-6. 2006406. 583518. free.
  20. Monier. Louis. 1980. Evaluation and comparison of two efficient probabilistic primality testing algorithms. Theoretical Computer Science. 12. 1. 97–108. 10.1016/0304-3975(80)90007-9. 582244. free.
  21. This form of sub-exponential time is valid for all

    \varepsilon>0

    . A more precise form of the complexity can be given as
    O
    d\left(\exp\sqrt[3]{64
    9

    b(logb)2}\right).

  22. Book: Le Gall . François . Urrutia . Floren . Czumaj . Artur . Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . 2018 . Society for Industrial and Applied Mathematics . 978-1-61197-503-1 . Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor . 10.1137/1.9781611975031.67. 33396059 .
  23. Knight . Philip A. . May 1995 . Fast rectangular matrix multiplication and QR decomposition . Linear Algebra and its Applications . 221 . 69–81 . 10.1016/0024-3795(93)00230-w . 0024-3795. free .
  24. Book: Rote, G. . Division-free algorithms for the determinant and the pfaffian: algebraic and combinatorial approaches . http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf . Computational discrete mathematics . Springer . 2001 . 3-540-45506-X . 119–135 .
  25. Book: Theorem 6.6 . 241. The Design and Analysis of Computer Algorithms. Alfred V.. Aho. Alfred Aho. John E.. Hopcroft. John Hopcroft. Jeffrey D.. Ullman. Jeffrey Ullman. Addison-Wesley. 1974 . 978-0-201-00029-0.
  26. Book: J.B. . Fraleigh . R.A. . Beauregard . Linear Algebra . Addison-Wesley . 3rd . 1987 . 978-0-201-15459-7 . 95 .
  27. Book: Henry . Cohn . Robert . Kleinberg . Balazs . Szegedy . Chris . Umans . math.GR/0511460 . Group-theoretic Algorithms for Matrix Multiplication . Proceedings of the 46th Annual Symposium on Foundations of Computer Science . 2005 . IEEE . 0-7695-2468-0 . 379–388 . 10.1109/SFCS.2005.39. 6429088 .