The following tables list the

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

of various

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s for common

mathematical operation In mathematics, an operation is a function which takes zero or more input values (also called "''operands''" or "arguments") to a well-defined output value. The number of operands is the arity of the operation. The most commonly studied operat ...

s. Here, complexity refers to the

time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

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(n)

below stands in for the complexity of the chosen multiplication algorithm.

Arithmetic functions

This table lists the complexity of mathematical operations on integers.

Algebraic functions

Special functions

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

Elementary functions

The

elementary function In mathematics, an elementary function is a function of a single variable (typically real or complex) that is defined as taking sums, products, roots and compositions of finitely many polynomial, rational, trigonometric, hyperbolic, a ...

s are constructed by composing arithmetic operations, the

exponential function The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, ...

(

\exp

), the

natural logarithm The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...

(

\log

trigonometric function In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in ...

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 and hence invertible by means of Newton's method. In particular, if either

\exp

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

(M(n))

Non-elementary functions

Mathematical constants

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

n

correct digits.

Number theory

Algorithms for number theoretical calculations are studied in

computational number theory In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorith ...

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 In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can b ...

or operations on a

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...

. In 2005, Henry Cohn, Robert Kleinberg,

Balázs Szegedy Balázs Szegedy is a Hungarian mathematician whose research concerns combinatorics and graph theory. Szegedy earned a master's degree in 1998 and a PhD in 2003 from Eötvös Loránd University in Budapest.

, 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 Transform may refer to: Arts and entertainment * Transform (scratch), a type of scratch used by turntablists * ''Transform'' (Alva Noto album), 2001 * ''Transform'' (Howard Jones album) or the title song, 2019 * ''Transform'' (Powerman 5000 album ...

of functions (particularly

integral transform In mathematics, an integral transform maps a function from its original function space into another function space via integration, where some of the properties of the original function might be more easily characterized and manipulated than i ...

s) are widely used in all areas of mathematics, particularly

analysis Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (3 ...

and

signal processing Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing '' signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...