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 multitape Turing machine. See big O notation for an explanation of the notation used.
Note: Due to the variety of multiplication algorithms, M below stands in for the complexity of the chosen multiplication algorithm.

Arithmetic functions

Operation	Input	Output	Algorithm	Complexity
Addition	Two n-digit numbers N, N	One n+1-digit number	Schoolbook addition with carry	Θ, Θ
Subtraction	Two n-digit numbers N, N	One n+1-digit number	Schoolbook subtraction with borrow	Θ, Θ
Multiplication	Two n-digit numbers	One 2n-digit number	Schoolbook long multiplication
Multiplication	Two n-digit numbers	One 2n-digit number	Karatsuba algorithm
Multiplication	Two n-digit numbers	One 2n-digit number	3-way Toom–Cook multiplication
Multiplication	Two n-digit numbers	One 2n-digit number	-way Toom–Cook multiplication
Multiplication	Two n-digit numbers	One 2n-digit number	Mixed-level Toom–Cook
Multiplication	Two n-digit numbers	One 2n-digit number	Schönhage–Strassen algorithm
Multiplication	Two n-digit numbers	One 2n-digit number	Fürer's algorithm
Multiplication	Two n-digit numbers	One 2n-digit number	Harvey-Hoeven algorithm
Division	Two n-digit numbers	One n-digit number	Schoolbook long division
Division	Two n-digit numbers	One n-digit number	Burnikel-Ziegler Divide-and-Conquer Division
Division	Two n-digit numbers	One n-digit number	Newton–Raphson division
Square root	One n-digit number	One n-digit number	Newton's method
Modular exponentiation	Two n-digit integers and a k-bit exponent	One n-digit integer	Repeated multiplication and reduction
Modular exponentiation	Two n-digit integers and a k-bit exponent	One n-digit integer	Exponentiation by squaring
Modular exponentiation	Two n-digit integers and a k-bit exponent	One n-digit integer	Exponentiation with Montgomery reduction

Algebraic functions

Operation	Input	Output	Algorithm	Complexity
Polynomial evaluation	One polynomial of degree n with fixed-size coefficients	One fixed-size number	Direct evaluation	Θ
Polynomial evaluation	One polynomial of degree n with fixed-size coefficients	One fixed-size number	Horner's method	Θ
Polynomial gcd	Two polynomials of degree n with fixed-size integer coefficients	One polynomial of degree at most n	Euclidean algorithm	O
Polynomial gcd	Two polynomials of degree n with fixed-size integer coefficients	One polynomial of degree at most n	Fast Euclidean algorithm	O

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

Algorithm	Applicability	Complexity
Taylor series; repeated argument reduction = exp and direct summation	exp, log, sin, cos, arctan	O
Taylor series; FFT-based acceleration	exp, log, sin, cos, arctan	O n^1/3
Taylor series; [binary splitting + bit-burst algorithm	exp, log, sin, cos, arctan	O
Arithmetic–geometric mean iteration	exp, log, sin, cos, arctan	O

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

Non-elementary functions

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
Square root of 2,	Newton's method	O
Euler's number, e	Binary splitting of the Taylor series for the exponential function	O
Euler's number, e	Newton inversion of the natural logarithm	O
Pi, π	Binary splitting of the arctan series in Machin's formula	O
Pi, π	Gauss–Legendre algorithm	O
Euler's constant, γ	Sweeney's method	O

Number theory

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

Operation	Input	Output	Algorithm	Complexity
Greatest common divisor	Two n-digit integers	One integer with at most n digits	Euclidean algorithm	O
Greatest common divisor	Two n-digit integers	One integer with at most n digits	Binary GCD algorithm	O
Greatest common divisor	Two n-digit integers	One integer with at most n digits	Left/right k-ary binary GCD algorithm	O
Greatest common divisor	Two n-digit integers	One integer with at most n digits	Stehlé–Zimmermann algorithm	O
Greatest common divisor	Two n-digit integers	One integer with at most n digits	Schönhage controlled Euclidean descent algorithm	O
Jacobi symbol	Two n-digit integers	0, −1, or 1	Schönhage controlled Euclidean descent algorithm	O
Jacobi symbol	Two n-digit integers	0, −1, or 1	Stehlé–Zimmermann algorithm	O
Factorial	A positive integer less than m	One O-digit integer	Bottom-up multiplication	O
Factorial	A positive integer less than m	One O-digit integer	Binary splitting	O
Factorial	A positive integer less than m	One O-digit integer	Exponentiation of the prime factors of m	O, O
Primality test	A n-digit integer	True or false	AKS primality test	O or, O, assuming Agrawal's conjecture
Primality test	A n-digit integer	True or false	Elliptic curve primality proving	heuristically
Primality test	A n-digit integer	True or false	Baillie-PSW primality test
Primality test	A n-digit integer	True or false	Miller–Rabin primality test
Primality test	A n-digit integer	True or false	Solovay–Strassen primality test
Integer factorization	A b-bit input integer	A set of factors	General number field sieve	O
Integer factorization	A b-bit input integer	A set of factors	Shor's algorithm	, on a quantum computer

Matrix algebra

The following complexity figures assume that arithmetic with individual elements has complexity O, as is the case with fixed-precision floating-point arithmetic or operations on a finite field.

Operation	Input	Output	Algorithm	Complexity
Matrix multiplication	Two n×n matrices	One n×n matrix	Schoolbook matrix multiplication	O
Matrix multiplication	Two n×n matrices	One n×n matrix	Strassen algorithm	O
Matrix multiplication	Two n×n matrices	One n×n matrix	Coppersmith–Winograd algorithm	O
Matrix multiplication	Two n×n matrices	One n×n matrix	Optimized CW-like algorithms	O
Matrix multiplication	One n×m matrix & one m×p matrix	One n×p matrix	Schoolbook matrix multiplication	O
Matrix multiplication	One n×⌈n⌉ matrix & one ⌈n⌉×n matrix	One n×n matrix	Algorithms given in	, where upper bounds on are given in
Matrix inversion	One n×n matrix	One n×n matrix	Gauss–Jordan elimination	O
Matrix inversion	One n×n matrix	One n×n matrix	Strassen algorithm	O
Matrix inversion	One n×n matrix	One n×n matrix	Coppersmith–Winograd algorithm	O
Matrix inversion	One n×n matrix	One n×n matrix	Optimized CW-like algorithms	O
Singular value decomposition	One m×n matrix	One m×m matrix, one m×n matrix, & one n×n matrix	Bidiagonalization and QR algorithm	O
Singular value decomposition	One m×n matrix	One m×n matrix, one n×n matrix, & one n×n matrix	Bidiagonalization and QR algorithm	O
Determinant	One n×n matrix	One number	Laplace expansion	O
Determinant	One n×n matrix	One number	Division-free algorithm	O
Determinant	One n×n matrix	One number	LU decomposition	O
Determinant	One n×n matrix	One number	Bareiss algorithm	O
Determinant	One n×n matrix	One number	Fast matrix multiplication	O
Back substitution	Triangular matrix	n solutions	Back substitution	O

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.
Because of the possibility of blockwise inverting a matrix, where an inversion of an matrix requires inversion of two half-sized matrices and six multiplications between two half-sized matrices, and since matrix multiplication has a lower bound of operations, it can be shown that a divide and conquer algorithm that uses blockwise inversion to invert a matrix runs with the same time complexity as the matrix multiplication algorithm that is used internally.

Transforms

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

Operation	Input	Output	Algorithm	Complexity
Discrete Fourier transform	Finite data sequence of size n	Set of complex numbers	Fast Fourier transform	O

Popular movies

The Hunger Games (film) - 2012 American dystopian action thriller science fiction-adventure film directed by Gary Ross and based on Suzanne Collins’s 2008 novel of the same name. It is the first insta...
untitled Captain Marvel sequel - part of Marvel Cinematic Universe....
Killers of the Flower Moon (film project) - Killers of the Flower Moon - film project in United States of America. It was presented as drama, detective fiction, thriller. The film project starred Leonardo Dicaprio, Robert De Niro. Director of...
Five Nights at Freddy's (film) - Five Nights at Freddy's - film published in 2017 in United States of America. Scenarist of the film - Scott Cawthon....

Popular books

Book of Revelation - The Book of Revelation is the final book of the New Testament, and consequently is also the final book of the Christian Bible. Its title is derived from the first word of the Koine Greek text: apok...
Book of Genesis - account of the creation of the world, the early history of humanity, Israel's ancestors and the origins...
Gospel of Matthew - The Gospel According to Matthew is the first book of the New Testament and one of the three synoptic gospels. It tells how Israel's Messiah, rejected and executed in Israel, pronounces judgement on ...
Michelin Guide - Michelin Guides are a series of guide books published by the French tyre company Michelin for more than a century. The term normally refers to the annually published Michelin Red Guide , the oldest...
Psalms - The Book of Psalms , commonly referred to simply as Psalms , the Psalter or "the Psalms", is the first book of the Ketuvim , the third section of the Hebrew Bible, and thus a book of th...
Ecclesiastes - Ecclesiastes is one of 24 books of the Tanakh , where it is classified as one of the Ketuvim . Originally written c. 450–200 BCE, it is also among the canonical Wisdom literature of the Old Tes...
The 48 Laws of Power - non-fiction book by American author Robert Greene. The book...

Popular television series

The Crown (TV series) - historical drama web television series about the reign of Queen Elizabeth II, created and principally written by Peter Morgan, and produced by Left Bank Pictures and Sony Pictures Tel...
Friends - American sitcom television series, created by David Crane and Marta Kauffman, which aired on NBC from September 22, 1994, to May 6, 2004, lasting ten seasons. With an ensemble cast sta...
Young Sheldon - spin-off prequel to The Big Bang Theory and begins with the character Sheldon...
Modern Family - American television mockumentary family sitcom created by Christopher Lloyd and Steven Levitan for the American Broadcasting Company. It ran for eleven seasons, from September 23...
Loki (TV series) - upcoming American web television miniseries created for Disney+ by Michael Waldron, based on the Marvel Comics character of the same name. It is set in the Marvel Cinematic Universe, shar...
Game of Thrones - American fantasy drama television series created by David Benioff and D. B. Weiss for HBO. It...
Shameless (American TV series) - American comedy-drama television series developed by John Wells which debuted on Showtime on January 9, 2011. It...