Computational complexity of mathematical operations

The following tables list the computational complexity of various algorithms for common mathematical operations.

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

This table lists the complexity of mathematical operations on integers.

On stronger computational models, specifically a pointer machine and consequently also a unit-cost random-access machine it is possible to multiply two n-bit numbers in time O(n).

In practice this means that we assume them to be machine integers.

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.

refers to the number of digits of precision at which the function is to be evaluated.

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

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 2005, Henry Cohn, 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.