Polynomial Time

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 O(n^k) for some nonnegative integer k, where n 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 pi and e, can also be done in polynomial time.

See also

Complexity Theory, NP-Problem, P-Problem

This entry contributed by David Terr

Explore with Wolfram|Alpha


More things to try:

Cite this as:

Terr, David. "Polynomial Time." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications