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 Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s for common
mathematical operation
In mathematics, an operation is a function from a set to itself. For example, an operation on real numbers will take in real numbers and return a real number. An operation can take zero or more input values (also called "'' operands''" or "argu ...
s.
Here, complexity refers to the
time complexity
In theoretical 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 ...
of performing computations on a
multitape Turing machine.
See
big O notation
Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
for an explanation of the notation used.
Note: Due to the variety of multiplication algorithms,
below stands in for the complexity of the chosen multiplication algorithm.
Arithmetic functions
This table lists the complexity of mathematical operations on integers.
On stronger computational models, specifically a
pointer machine
In theoretical computer science, a pointer machine is an atomistic abstract computational machine whose storage structure is a graph. A pointer algorithm could also be an algorithm restricted to the pointer machine model.
Some particular types o ...
and consequently also a
unit-cost random-access machine it is possible to multiply two -bit numbers in time ''O''(''n'').
Algebraic functions
Here we consider operations over polynomials and 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. For this section
indicates the time needed for multiplying two polynomials of degree at most
.
[
]
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 natural logarithm
The natural logarithm of a number is its logarithm to the base of a logarithm, base of the e (mathematical constant), mathematical constant , which is an Irrational number, irrational and Transcendental number, transcendental number approxima ...
(), 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 all ...
s (), 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 or in the complex domain can be computed with some complexity, then that complexity is attainable for all other elementary functions.
Below, the size refers to the number of digits of precision at which the function is to be evaluated.
It is not known whether 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 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
In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a ''significand'' (a Sign (mathematics), signed sequence of a fixed number of digits in some Radix, base) multiplied by an integer power of that ba ...
or operations on a finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
.
In 2005, Henry Cohn
Henry Cohn is an American mathematician. He is a principal researcher at Microsoft Research and an adjunct professor at Massachusetts Institute of Technology, MIT.
Cohn graduated from Harvard University in 2000 with a doctorate in mathematics. Co ...
, 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.
Transforms
Algorithms for computing transforms of functions (particularly integral transform
In mathematics, an integral transform is a type of transform that 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 charac ...
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 (38 ...
and signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, Scalar potential, potential fields, Seismic tomograph ...
.
Notes
References
Further reading
*
*
{{refend
Computer arithmetic algorithms
Computational complexity theory
Mathematics-related lists
Number theoretic algorithms
Unsolved problems in computer science