The following tables list the computational complexity 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 Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

s for common

mathematical operation In mathematics, an operation is a Function (mathematics), 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 c ...

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

of performing computations on a

multitape Turing machine A multi-tape Turing machine is a variant of the Turing machine that utilizes several tapes. Each tape has its own head for reading and writing. Initially, the input appears on tape 1, and the others start out blank. This model intuitively seems m ...

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

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

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

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

. In 2005,

Henry Cohn Henry Cohn is an American mathematician. He is a principal researcher at Microsoft Research and an adjunct professor at MIT. In collaboration with Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska, he solved the sphere pa ...

Robert Kleinberg Robert David Kleinberg (also referred to as Bobby Kleinberg) is an American theoretical computer scientist and professor of Computer Science at Cornell University. Early life Robert Kleinberg was one of the finalists at the 1989 Mathcounts. He wa ...

, Balázs Szegedy, and

Chris Umans Christopher Umans is a professor of Computer Science in the Computing and Mathematical Sciences Department at the California Institute of Technology. He is known for work on algorithms, computational complexity, algebraic complexity, and hardness ...

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

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