polynomial time

Show Summary Details

Quick Reference

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.

f(n) ≤ p(n) for all n,

Subjects: Computing.

Reference entries