computational complexity of mathematical operations

{{Short description|Algorithmic runtime requirements for common math procedures}}

File:comparison computational complexity.svg

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.{{cite book |first1=A. |last1=Schönhage |first2=A.F.W. |last2=Grotefeld |first3=E. |last3=Vetter |title=Fast Algorithms—A Multitape Turing Machine Implementation |publisher=BI Wissenschafts-Verlag |date=1994 |isbn=978-3-411-16891-0 |pages= |oclc=897602049}} 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.

class="wikitable" style="width: auto"

!Operation

!Input

!Output

!Algorithm

!Complexity

Addition

|Two $n$ -digit numbers

|One $n+1$ -digit number

|Schoolbook addition with carry

| $\Theta(n)$

Subtraction

|Two $n$ -digit numbers

|One $n$ -digit number

|Schoolbook subtraction with borrow

| $\Theta(n)$

rowspan=7|Multiplication

|rowspan=7|Two $n$ -digit numbers

|rowspan=7|One $2n$ -digit number

|Schoolbook long multiplication

| $O\mathord\left(n^{2}\right)$

Karatsuba algorithm

| $O\mathord\left(n^{1.585}\right)$

3-way Toom–Cook multiplication

| $O\mathord\left(n^{1.465}\right)$

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){{harvnb|Knuth|1997}}

| $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{{cite journal |last1=Harvey |first1=D. |last2=Van Der Hoeven |first2=J. |title=Integer multiplication in time O (n log n) |journal=Annals of Mathematics |volume=193 |issue=2 |pages=563–617 |date=2021 |doi=10.4007/annals.2021.193.2.4 |s2cid=109934776 |url=https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf}}{{cite journal |first=Erica |last=Klarreich |title=Multiplication hits the speed limit |journal=Commun. ACM |volume=63 |issue=1 |pages=11–13 |date=December 2019 |doi=10.1145/3371387 |s2cid=209450552 |url=}}

| $O(n \log n)$

rowspan=3|Division

|rowspan=3|Two $n$ -digit numbers

|rowspan=3|One $n$ -digit number

|Schoolbook long division

| $O\mathord\left(n^{2}\right)$

Burnikel–Ziegler Divide-and-Conquer Division{{cite book |last1=Burnikel |first1=Christoph |first2=Joachim |last2=Ziegler |title=Fast Recursive Division |publisher=MPI Informatik Bibliothek & Dokumentation |series=Forschungsberichte des Max-Planck-Instituts für Informatik |date=1998 |id=MPII-98-1-022 |location=Saarbrücken |oclc=246319574}}

| $O(M(n) \log n)$

Newton–Raphson division

| $O(M(n))$

Square root

|One $n$ -digit number

|One $n/2$ -digit number

|Newton's method

| $O(M(n))$

rowspan=3|Modular exponentiation

|rowspan=3|Two $n$ -digit integers and a $k$ -bit exponent

|rowspan=3|One $n$ -digit integer

|Repeated multiplication and reduction

| $O\mathord\left(M(n) \, 2^{k}\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 {{mvar|n}}-bit numbers in time O(n).{{cite journal |last1=Schönhage |first1=Arnold |title=Storage Modification Machines |journal=SIAM Journal on Computing |date=1980 |volume=9 |issue=3 |pages=490–508 |doi=10.1137/0209036}}

Algebraic functions

Here we consider operations over polynomials and {{mvar|n}} 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.

class="wikitable"

!Operation

!Input

!Output

!Algorithm

!Complexity

rowspan=2|Polynomial evaluation

|rowspan=2| One polynomial of degree $n$ with integer coefficients

|rowspan=2| One number

|Direct evaluation

| $\Theta(n)$

Horner's method

| $\Theta(n)$

rowspan=2|Polynomial gcd (over

\mathbb{Z}[x]

F[x]

)

|rowspan=2| Two polynomials of degree $n$ with integer coefficients

|rowspan=2| One polynomial of degree at most $n$

|Euclidean algorithm

| $O\mathord\left(n^{2}\right)$

Fast Euclidean algorithm (Lehmer){{Citation needed|date=September 2023}}

| $O(M(n) \log n)$

Special functions

Many of the methods in this section are given in Borwein & Borwein.{{cite book |first1=J. |last1=Borwein |first2=P. |last2=Borwein |title=Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity |publisher=Wiley |date=1987 |isbn=978-0-471-83138-9 |oclc=755165897}}

= 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.

class="wikitable"

!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{{cite book |first1=David |last1=Chudnovsky |first2=Gregory |last2=Chudnovsky |chapter=Approximations and complex multiplication according to Ramanujan |chapter-url= |title=Ramanujan revisited: Proceedings of the Centenary Conference |publisher=Academic Press |date=1988 |isbn=978-0-01-205856-5 |pages=375–472 |url=}}

| $\exp, \log, \sin, \cos, \arctan$

| $O\mathord\left(M(n) (\log n)^2\right)$

Arithmetic–geometric mean iteration{{cite book |arxiv=1004.3412 |first=Richard P. |last=Brent |chapter=Multiple-precision zero-finding methods and the complexity of elementary function evaluation |chapter-url={{GBurl|UZriBQAAQBAJ|p=151}} |editor-first=J.F. |editor-last=Traub |title=Analytic Computational Complexity |publisher=Elsevier |date=2014 |orig-date=1975 |isbn=978-1-4832-5789-1 |pages=151–176 |url=}}

| $\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

{{math| $\Omega$ }} $(M(n))$ .

= Non-elementary functions =

class="wikitable"

!Function

!Input

!Algorithm

!Complexity

rowspan=3|Gamma function

| $n$ -digit number

|Series approximation of the incomplete 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

integer.

|Arithmetic-geometric mean iteration

| $O(M(n) \log n)$

rowspan=2|Hypergeometric function

{}_p\!F_q

| $n$ -digit number

|(As described in Borwein & Borwein)

| $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)$

= Mathematical constants =

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

class="wikitable"

!Constant

!Algorithm

!Complexity

Golden ratio,

\phi

|Newton's method

| $O(M(n))$

Square root of 2,

\sqrt{2}

|Newton's method

| $O(M(n))$

rowspan=2|Euler's number,

e

|Binary splitting of the Taylor series for the exponential function

| $O(M(n) \log n)$

Newton inversion of the natural logarithm

| $O(M(n) \log n)$

rowspan=2|Pi,

\pi

|Binary splitting of the arctan series in Machin's formula

| $O\mathord\left(M(n) (\log n)^2\right)$ {{citation|title=The Borwein Brothers, Pi and the AGM|author=Richard P. Brent|series=Springer Proceedings in Mathematics & Statistics|year=2020|volume=313|doi=10.1007/978-3-030-36568-4|arxiv=1802.07558|isbn=978-3-030-36567-7|s2cid=214742997}}

Gauss–Legendre algorithm

| $O(M(n) \log n)$

Euler's constant,

\gamma

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

| $O\mathord\left(M(n) (\log n)^2\right)$

Number theory

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

class="wikitable"

!Operation

!Input

!Output

!Algorithm

!Complexity

rowspan=5|Greatest common divisor

|rowspan=5|Two $n$ -digit integers

|rowspan=5|One integer with at most $n$ digits

|Euclidean algorithm

| $O\mathord\left(n^{2}\right)$

Binary GCD algorithm

| $O\mathord\left(n^2\right)$

Left/right k-ary binary GCD algorithm{{cite journal |first= J. |last=Sorenson | title = Two Fast GCD Algorithms | journal = Journal of Algorithms | volume = 16 | issue = 1| pages = 110–144 | year = 1994 | doi=10.1006/jagm.1994.1006}}

| $O\mathord\left(\frac{n^{2}}{\log n}\right)$

Stehlé–Zimmermann algorithm{{cite book |first1=R. |last1=Crandall |first2=C. |last2=Pomerance |chapter=Algorithm 9.4.7 (Stehlé-Zimmerman binary-recursive-gcd) |chapter-url={{GBurl|ZXjHKPS1LEAC|p=471}} |pages=471–3 |title=Prime Numbers – A Computational Perspective |publisher=Springer |edition=2nd |date=2005 |isbn=978-0-387-28979-3}}

| $O(M(n) \log n)$

Schönhage controlled Euclidean descent algorithm{{cite journal | author = Möller N | title = On Schönhage's algorithm and subquadratic integer gcd computation | journal = Mathematics of Computation | volume = 77 | issue = 261 | pages = 589–607 | doi = 10.1090/S0025-5718-07-02017-0 | year = 2008 | url=http://www.lysator.liu.se/~nisse/archive/sgcd.pdf| bibcode = 2008MaCom..77..589M | doi-access = free }}

| $O(M(n) \log n)$

rowspan=2|Jacobi symbol

|rowspan=2|Two $n$ -digit integers

|rowspan=2| $0$ , $-1$ or $1$

|Schönhage controlled Euclidean descent algorithm{{cite web|url=http://cr.yp.to/papers/nonsquare.ps|title=Faster Algorithms to Find Non-squares Modulo Worst-case Integers|last=Bernstein |first=D.J.}}

| $O(M(n) \log n)$

Stehlé–Zimmermann algorithm{{cite book |arxiv=1004.2091 |first1=Richard P. |last1=Brent |first2=Paul |last2=Zimmermann |chapter=An

O(M(n) \log n)

algorithm for the Jacobi symbol|year=2010 |title=International Algorithmic Number Theory Symposium |pages=83–95 |publisher=Springer |doi=10.1007/978-3-642-14518-6_10 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-14518-6_10 |isbn=978-3-642-14518-6|s2cid=7632655 }}

| $O(M(n) \log n)$

rowspan=3|Factorial

|rowspan=3|A positive integer less than $m$

|rowspan=3|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

| $O(M(m \log m) \log \log m)$ ,{{cite journal | last1 = Borwein | first1 = P. | year = 1985 | title = On the complexity of calculating factorials | journal = Journal of Algorithms | volume = 6 | issue = 3| pages = 376–380 | doi=10.1016/0196-6774(85)90006-9}}
$O(M(m \log m))$

rowspan=5|Primality test

|rowspan=5|A $n$ -digit integer

|rowspan=5|True or false

|AKS primality test

| $O\mathord\left(n^{6+o(1)}\right)$ {{cite journal |first1=H.W. |last1=Lenstra jr. |first2=Carl |last2=Pomerance |author1-link=Hendrik Lenstra |author2-link=Carl Pomerance |title=Primality testing with Gaussian periods |journal=Journal of the European Mathematical Society |year=2019 |volume=21 |issue=4 |pages=1229–69 |doi=10.4171/JEMS/861 |hdl=21.11116/0000-0005-717D-0 |url=http://www.math.dartmouth.edu/~carlp/aks041411.pdf}}{{cite book|title=An epsilon of room, II: Pages from year three of a mathematical blog|last=Tao|first=Terence|publisher=American Mathematical Society|year=2010|isbn=978-0-8218-5280-4|series=Graduate Studies in Mathematics|volume=117 |pages=82–86|contribution=1.11 The AKS primality test|doi=10.1090/gsm/117|mr=2780010|author-link=Terence Tao|contribution-url=https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/}}
$O(n^{3})$ , assuming Agrawal's conjecture

Elliptic curve primality proving

| $O\mathord\left(n^{4+\varepsilon}\right)$ heuristically{{cite journal|last=Morain|first=F.|year=2007|title=Implementing the asymptotically fast version of the elliptic curve primality proving algorithm|journal=Mathematics of Computation|volume=76|issue=257|pages=493–505|arxiv=math/0502097|bibcode=2007MaCom..76..493M|doi=10.1090/S0025-5718-06-01890-4|mr=2261033|s2cid=133193}}

Baillie–PSW primality test

| $O\mathord\left(n^{2+\varepsilon}\right)$ {{cite journal|first1=Carl |last1=Pomerance|first2=John L. |last2=Selfridge|author-link2=John L. Selfridge|first3=Samuel S. |last3=Wagstaff, Jr.|author-link3=Samuel S. Wagstaff, Jr.|date=July 1980|title=The pseudoprimes to 25·10⁹|url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf|journal=Mathematics of Computation|volume=35|issue=151|pages=1003–26|doi=10.1090/S0025-5718-1980-0572872-7|jstor=2006210|author-link1=Carl Pomerance|doi-access=free}}{{cite journal|first1=Robert |last1=Baillie|first2=Samuel S. |last2=Wagstaff, Jr.|author-link2=Samuel S. Wagstaff, Jr.|date=October 1980|title=Lucas Pseudoprimes|url=http://mpqs.free.fr/LucasPseudoprimes.pdf|journal=Mathematics of Computation|volume=35|issue=152|pages=1391–1417|doi=10.1090/S0025-5718-1980-0583518-6|jstor=2006406|mr=583518|doi-access=free}}

Miller–Rabin primality test

| $O\mathord\left(kn^{2+\varepsilon}\right)$ {{cite journal|last=Monier|first=Louis|year=1980|title=Evaluation and comparison of two efficient probabilistic primality testing algorithms|journal=Theoretical Computer Science|volume=12|issue=1|pages=97–108|doi=10.1016/0304-3975(80)90007-9|mr=582244|doi-access=free}}

Solovay–Strassen primality test

| $O\mathord\left(kn^{2+\varepsilon}\right)$

rowspan=2|Integer factorization

|rowspan=2|A $b$ -bit input integer

|rowspan=2|A set of factors

|General number field sieve

| $O\mathord\left((1+\varepsilon)^b\right)$ This form of sub-exponential time is valid for all $\varepsilon > 0$ . A more precise form of the complexity can be given as $O\mathord\left(\exp\sqrt[3]{\frac{64}{9} b (\log b)^2}\right).$

Shor's algorithm

| $O(M(b) b)$ , 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.

class="wikitable"

!Operation

!Input

!Output

!Algorithm

!Complexity

rowspan=6|Matrix multiplication

|rowspan=4|Two $n \times n$ matrices

|rowspan=4|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

{{Citation

| last1=Alman

| first1=Josh

| last2=Williams

| first2=Virginia Vassilevska

| contribution=A Refined Laser Method and Faster Matrix Multiplication

| year = 2020 |doi=10.1137/1.9781611976465.32

| arxiv=2010.05846

| title = 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)

| pages=522–539

| isbn=978-1-61197-646-5

| s2cid=222290442

|url=https://www.siam.org/conferences/cm/program/accepted-papers/soda21-accepted-papers

}}{{Citation | last1=Davie | first1=A.M. | last2=Stothers | first2=A.J. | title=Improved bound for complexity of matrix multiplication|journal=Proceedings of the Royal Society of Edinburgh|volume=143A| issue=2 |pages=351–370|year=2013|doi=10.1017/S0308210511001648| s2cid=113401430 }}{{Citation | last1=Vassilevska Williams | first1=Virginia |author-link= Virginia Vassilevska Williams | title=Breaking the Coppersmith-Winograd barrier: Multiplying matrices in O(n^2.373) time | url=https://www.scribd.com/document/397495001/Breaking-the-Coppersmith-Winograd-Barrier-for-Matrix-Multiplication-Algorithms | year=2014 }}{{Citation | last1=Le Gall | first1=François | contribution=Powers of tensors and fast matrix multiplication | year = 2014 | arxiv=1401.7714 | title = Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation — ISSAC '14| bibcode=2014arXiv1401.7714L | title-link=ISSAC | page=23 | doi=10.1145/2608628.2627493 | isbn=9781450325011 | s2cid=353236 }} (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 {{cite book |last1=Le Gall |first1=François |last2=Urrutia |first2=Floren |editor1-last=Czumaj |editor1-first=Artur |title=Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms |date=2018 |publisher=Society for Industrial and Applied Mathematics |isbn=978-1-61197-503-1 |chapter=Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor |doi=10.1137/1.9781611975031.67|s2cid=33396059 }}

| $O(n^{\omega(k)+\epsilon})$ , where upper bounds on $\omega(k)$ are given in

rowspan=4|Matrix inversion

|rowspan=4|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)$

rowspan=2|Singular value decomposition

|rowspan=2|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$ )

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 {{Cite journal |last=Knight |first=Philip A. |date=May 1995 |title=Fast rectangular matrix multiplication and QR decomposition |journal=Linear Algebra and Its Applications |volume=221 |pages=69–81 |doi=10.1016/0024-3795(93)00230-w |issn=0024-3795|doi-access=free }}

| $O\mathord\left(mn^{1+\frac{1}{4-\omega}}\right)$
( $m \geq n$ )

rowspan=5|Determinant

|rowspan=5|One $n \times n$ matrix

|rowspan=5|One number

|Laplace expansion

| $O(n!)$

Division-free algorithm{{cite book |first=G. |last=Rote |chapter=Division-free algorithms for the determinant and the pfaffian: algebraic and combinatorial approaches |chapter-url=http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf |title=Computational discrete mathematics |publisher=Springer |date=2001 |isbn=3-540-45506-X |pages=119–135 |url=}}

| $O\mathord\left(n^4\right)$

LU decomposition

| $O(n^3)$

Bareiss algorithm

| $O\mathord\left(n^3\right)$

Fast matrix multiplication{{cite book |chapter=Theorem 6.6 |page=241|title=The Design and Analysis of Computer Algorithms|first1=Alfred V.|last1=Aho|author1-link=Alfred Aho|first2=John E.|last2=Hopcroft|author2-link=John Hopcroft|first3=Jeffrey D.|last3=Ullman|author3-link=Jeffrey Ullman|publisher=Addison-Wesley|year=1974 |isbn=978-0-201-00029-0}}

| $O\mathord\left(n^\psi\right)$

Back substitution

|Triangular matrix

| $n$ solutions

|Back substitution{{cite book |first1=J.B. |last1=Fraleigh |first2=R.A. |last2=Beauregard |title=Linear Algebra |publisher=Addison-Wesley |edition=3rd |date=1987 |isbn=978-0-201-15459-7 |pages=95 |url=}}

| $O\mathord\left(n^2\right)$

rowspan=3|Characteristic polynomial

|rowspan=3|One $n \times n$ matrix

|rowspan=3|One degree- $n$ polynomial

|Faddeev-LeVerrier algorithm

| $O(n^{\psi+1})$

Samuelson-Berkowitz algorithm

| $O(n^{\psi+1})$ (smaller constant factor)

Preparata-Sarwate algorithm{{Cite journal|last1=Preparata|first1=F.P.|last2=Sarwate|first2=D.V.|date=April 1978|title=An improved parallel processor bound in fast matrix inversion|journal=Information Processing Letters|volume=7|issue=3|pages=148–150|doi=10.1016/0020-0190(78)90079-0|doi-access=free}}{{Cite journal|last1=Galil|first1=Zvi|last2=Pan|first2=Victor|date=January 16, 1989|title=Parallel evaluation of the determinant and of the inverse of a matrix|journal=Information Processing Letters|volume=30|issue=1|pages=148–150|doi=10.1016/0020-0190(89)90173-7|doi-access=free}}, in which the

O(n^3)

term is reduced

| $O(n^{\psi+1/2}+n^3)$

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.{{cite book |first1=Henry |last1=Cohn |first2=Robert |last2=Kleinberg |first3=Balazs |last3=Szegedy |first4=Chris |last4=Umans |arxiv=math.GR/0511460 |chapter=Group-theoretic Algorithms for Matrix Multiplication |chapter-url= |title=Proceedings of the 46th Annual Symposium on Foundations of Computer Science |year=2005 |publisher=IEEE |isbn=0-7695-2468-0 |pages=379–388 |doi=10.1109/SFCS.2005.39|s2cid=6429088 }}

Transforms

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

class="wikitable"

!Operation

!Input

!Output

!Algorithm

!Complexity

rowspan=2|Discrete Fourier transform

|rowspan=2|Finite data sequence of size $n$

|rowspan=2|Set of complex numbers

|Schoolbook

| $O(n^2)$

Fast Fourier transform

| $O(n \log n)$

computational complexity of mathematical operations

Arithmetic functions

Algebraic functions

Special functions

= Elementary functions =

= Non-elementary functions =

= Mathematical constants =

Number theory

Matrix algebra

Transforms

Notes

References

Further reading