Computational complexity of mathematical operations

The following tables list the computational complexity of various algorithms for common mathematical operations.one m×p matrix The following tables list the computational complexity of various algorithms for common mathematical operations. Here, complexity refers to the time complexity 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. Many of the methods in this section are given in Borwein & Borwein. The elementary functions are constructed by composing arithmetic operations, the exponential function (exp), the natural logarithm (log), trigonometric functions (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)). This table gives the complexity of computing approximations to the given constants to n correct digits. Algorithms for number theoretical calculations are studied in computational number theory.