polynomial time

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.