Polynomial time is a bound of 
on the number of steps required by an algorithm
for a given input, where 
is a nonnegative integer
and 
measures the input size. 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.
Polynomial Time
See also
Bit Complexity, Complexity Theory, Linear Time, NP-Problem, P-Problem, Quasipolynomial Time, Unit-Time Job SchedulingThis entry contributed by David Terr
Explore with Wolfram|Alpha
Cite this as:
Weisstein, Eric W., with contributions by David Terr. "Polynomial Time." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PolynomialTime.html