The following tables list the running time

Analysis of algorithms

To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...

 of various algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s for common mathematical operations.

Here, complexity refers to the time complexity

Time complexity

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...

 of performing computations on a multitape Turing machine. See big O notation

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

 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

Operation	Input	Output	Algorithm	Complexity
Addition Addition Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....	Two n-digit numbers	One n+1-digit number	Schoolbook addition with carry	Θ(n)
Subtraction Subtraction In arithmetic, subtraction is one of the four basic binary operations; it is the inverse of addition, meaning that if we start with any number and add any number and then subtract the same number we added, we return to the number we started with...	Two n-digit numbers	One n+1-digit number	Schoolbook subtraction with borrow	Θ(n)
Multiplication Multiplication Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....	Two n-digit numbers	One 2n-digit number	Schoolbook long multiplication	O(n2)
			Karatsuba algorithm	O(n1.585)
			3-way Toom–Cook multiplication	O(n1.465)
			k-way Toom–Cook multiplication	O(nlog (2k − 1)/log k)
			Mixed-level Toom–Cook (Knuth 4.3.3-T)	O(n 2√(2 log n) log n)
			Schönhage–Strassen algorithm	O(n log n log log n)
			Fürer's algorithm Fürer's algorithm Fürer's algorithm is an integer multiplication algorithm for very large numbers possessing a very low asymptotic complexity. It was created in 2007 by Swiss mathematician Martin Fürer of Pennsylvania State University as an asymptotically faster algorithm than its predecessor, the...	O(n log n 2log* Iterated logarithm In computer science, the iterated logarithm of n, written  n , is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1...  n)
Division Division (mathematics) right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...	Two n-digit numbers	One n-digit number	Schoolbook long division Long division In arithmetic, long division is a standard procedure suitable for dividing simple or complex multidigit numbers. It breaks down a division problem into a series of easier steps. As in all division problems, one number, called the dividend, is divided by another, called the divisor, producing a...	O(n2)
			Newton's method Newton's method In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...	M(n)
Square root Square root In mathematics, a square root of a number x is a number r such that r2 = x, or, in other words, a number r whose square is x...	One n-digit number	One n-digit number	Newton's method	M(n)
Modular exponentiation Modular exponentiation Modular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography....	Two n-digit numbers and a k-bit exponent	One n-digit number	Repeated multiplication and reduction	O(2kM(n))
			Exponentiation by squaring Exponentiation by squaring Exponentiating by squaring is a general method for fast computation of large integer powers of a number. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add...	O(k M(n))
			Exponentiation with Montgomery reduction Montgomery reduction In arithmetic computation, Montgomery reduction is an algorithm introduced in 1985 by Peter Montgomery that allows modular arithmetic to be performed efficiently when the modulus is large ....	O(k M(n))

Schnorr and Stumpf conjectured that no fastest algorithm for multiplication exists.

Algebraic functions

Operation	Input	Output	Algorithm	Complexity
Polynomial Polynomial In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...  evaluation	One polynomial of degree n with fixed-size polynomial coefficients	One fixed-size number	Direct evaluation	Θ(n)
			Horner's method	Θ(n)
Polynomial gcd (over Z[x] or F[x])	Two polynomials of degree n with fixed-size polynomial coefficients	One polynomial of degree at most n	Euclidean algorithm	O(n2)
			Fast Euclidean algorithm	O(n (log n)2 log log n)

Elementary functions

The elementary functions are constructed by composing arithmetic operations, the exponential function

Exponential function

In mathematics, the exponential function is the function ex, where e is the number such that the function ex is its own derivative. The exponential function is used to model a relationship in which a constant change in the independent variable gives the same proportional change In mathematics,...

 (exp), the natural logarithm

Natural logarithm

The natural logarithm is the logarithm to the base e, where e is an irrational and transcendental constant approximately equal to 2.718281828...

 (log), trigonometric function

Trigonometric function

In mathematics, the trigonometric functions are functions of an angle. They are used to relate the angles of a triangle to the lengths of the sides of a triangle...

s (sin, cos), and their inverses. The complexity of an elementary function is equivalent to that of its inverse, since all elementary functions are analytic

Analytic function

In mathematics, an analytic function is a function that is locally given by a convergent power series. There exist both real analytic functions and complex analytic functions, categories that are similar in some ways, but different in others...

 and hence invertible by means of Newton's method. In particular, if either exp or log 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 Taylor series In mathematics, a Taylor series is a representation of a function as an infinite sum of terms that are calculated from the values of the function's derivatives at a single point.... ; repeated argument reduction (e.g. exp(2x) = [exp(x)]2) and direct summation	exp, log, sin, cos	O(n1/2 M(n))
Taylor series; FFT Fast Fourier transform A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple... -based acceleration	exp, log, sin, cos	O(n1/3 (log n)2 M(n))
Taylor series; binary splitting Binary splitting In mathematics, binary splitting is a technique for speeding up numerical evaluation of many types of series with rational terms. In particular, it can be used to evaluate hypergeometric series at rational points...  + bit burst method	exp, log, sin, cos	O((log n)2 M(n))
Arithmetic-geometric mean iteration	log	O(log n M(n))

It is not known whether O(log n M(n)) is the optimal complexity for elementary functions. The best known lower bound is the trivial bound Ω(M(n)).

Non-elementary functions

Function	Input	Algorithm	Complexity
Gamma function Gamma function In mathematics, the gamma function is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers...	n-digit number	Series approximation of the incomplete gamma function Incomplete gamma function In mathematics, the gamma function is defined by a definite integral. The incomplete gamma function is defined as an integral function of the same integrand. There are two varieties of the incomplete gamma function: the upper incomplete gamma function is for the case that the lower limit of...	O(n1/2 (log n)2 M(n))
	Fixed rational number	Hypergeometric series	O((log n)2 M(n))
	m/24, m an integer	Arithmetic-geometric mean iteration	O(log n M(n))
Hypergeometric function pFq	n-digit number	(As described in Borwein & Borwein)	O(n1/2 (log n)2 M(n))
	Fixed rational number	Hypergeometric series	O((log n)2 M(n))

Mathematical constants

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

Constant	Algorithm	Complexity
Golden ratio Golden ratio In mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989... , φ	Newton's method Newton's method In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...	O(M(n))
Square root of 2 Square root of 2 The square root of 2, often known as root 2, is the positive algebraic number that, when multiplied by itself, gives the number 2. It is more precisely called the principal square root of 2, to distinguish it from the negative number with the same property.Geometrically the square root of 2 is the... , √2	Newton's method	O(M(n))
Euler's number E (mathematical constant) The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base... , e	Binary splitting Binary splitting In mathematics, binary splitting is a technique for speeding up numerical evaluation of many types of series with rational terms. In particular, it can be used to evaluate hypergeometric series at rational points...  of the Taylor series for the exponential function	O(log n M(n))
	Newton inversion of the natural logarithm	O(log n M(n))
Pi Pi ' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants... , π	Binary splitting of the arctan series in Machin's formula	O((log n)2 M(n))
	Salamin–Brent algorithm	O(log n M(n))
Euler's constant Euler–Mascheroni constant The Euler–Mascheroni constant is a mathematical constant recurring in analysis and number theory, usually denoted by the lowercase Greek letter .... , γ	Sweeney's method (approximation in terms of the exponential integral Exponential integral In mathematics, the exponential integral is a special function defined on the complex plane given the symbol Ei.-Definitions:For real, nonzero values of x, the exponential integral Ei can be defined as... )	O((log n)2 M(n))

Number theory

Algorithms for number theoretical

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

 calculations are studied in computational number theory

Computational number theory

In mathematics, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations...

.

Operation	Input	Output	Algorithm	Complexity
Greatest common divisor Greatest common divisor In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...	Two n-digit numbers	One number with at most n digits	Euclidean algorithm Euclidean algorithm In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...	O(n2)
			Binary GCD algorithm Binary GCD algorithm The binary GCD algorithm, also known as Stein's algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. It gains a measure of efficiency over the ancient Euclidean algorithm by replacing divisions and multiplications with shifts, which are cheaper when...	O(n2)
			Left/Right k-ary Binary GCD algorithm	O(n2 / log n)
			Stehlé-Zimmermann algorithm	O(log n M(n))
			Schönhage controlled Euclidean descent algorithm	O(log n M(n))
Jacobi symbol Jacobi symbol The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in...	Two n-digit numbers	0, -1, or 1
			Schönhage controlled Euclidean descent algorithm	O(log n M(n))
			Stehlé-Zimmermann algorithm	O(log n M(n))
Factorial Factorial In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...	A fixed-size number m	One O(m log m)-digit number	Bottom-up multiplication	O(m2 log m)
			Binary splitting	O(log m M(m log m))
			Exponentiation of the prime factors of m	O(log log m M(m log m)), O(M(m log m))

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.

Operation	Input	Output	Algorithm	Complexity
Matrix multiplication Matrix multiplication In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...	Two n×n-matrices	One n×n-matrix	Schoolbook matrix multiplication	O(n3)
			Strassen algorithm Strassen algorithm In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication...	O(n2.807)
			Coppersmith–Winograd algorithm Coppersmith–Winograd algorithm In the mathematical discipline of linear algebra, the Coppersmith–Winograd algorithm, named after Don Coppersmith and Shmuel Winograd, is the asymptotically fastest known algorithm for square matrix multiplication. It can multiply two n \times n matrices in O time...	O(n2.376)
			Williams algorithm	O(n2.373)
Matrix multiplication	One n×m-matrix & One m×p-matrix	One n×p-matrix	Schoolbook matrix multiplication	O(nmp)
Matrix inversion	One n×n-matrix	One n×n-matrix	Gauss–Jordan elimination Gauss–Jordan elimination In linear algebra, Gauss–Jordan elimination is an algorithm for getting matrices in reduced row echelon form using elementary row operations. It is a variation of Gaussian elimination. Gaussian elimination places zeros below each pivot in the matrix, starting with the top row and working downwards....	O(n3)
			Strassen algorithm	O(n2.807)
			Coppersmith–Winograd algorithm	O(n2.376)
Determinant Determinant In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...	One n×n-matrix	One number with at most O(n log n) bits	Laplace expansion Laplace expansion In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression for the determinant |B| of...	O(n!)
			LU decomposition LU decomposition In linear algebra, LU decomposition is a matrix decomposition which writes a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. This decomposition is used in numerical analysis to solve systems of linear...	O(n3)
			Bareiss algorithm Bareiss algorithm In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm to calculate the determinant of a matrix with integer entries using only integer arithmetic; any divisions that are performed are guaranteed to be exact...	O(n3)
			Fast matrix multiplication	O(n2.376)
Back Substitution	Triangular matrix Triangular matrix In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where either all the entries below or all the entries above the main diagonal are zero...	n solutions	Back substitution	O(n2)

In 2005, Henry Cohn, Robert Kleinberg, Balázs Szegedy and Christopher Umans showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2. It has also been conjectured that no fastest algorithm for matrix multiplication exists, in light of the nearly 20 successive improvements leading to the Williams algorithm.