An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is for some nonnegative integer , where is the complexity of the input. Polynomial-time algorithms are said to be "fast." Most familiar mathematical operations such as addition, subtraction, multiplication, and division, as well as computing square roots, powers, and logarithms, can be performed in polynomial time. Computing the digits of most interesting mathematical constants, including and , can also be done in polynomial time.

This entry contributed by David Terr

CITE THIS AS:

Terr, David. "Polynomial Time." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/PolynomialTime.html