HOME

TheInfoList



OR:

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, 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. 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 M(n) indicates the time needed for multiplying two polynomials of degree at most n.


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 (\exp), 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 ...
(\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 all ...
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 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. 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 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