views updated

polynomial time A way of characterizing the complexity of an algorithm or program. If the number f(n) of elementary operations required to apply the algorithm of program to data of size n increases with n no more rapidly than a polynomial p(n), f(n) ← p(n) for all n,

then the algorithm or program is said to be executable in polynomial time. Here time is identified with steps in computation, such as invocations of primitive operations, execution of basic instructions, state transitions, etc. See also complexity measure, P=NP question.

About this article

polynomial time

Updated About encyclopedia.com content Print Article Share Article