Polynomial time refers to a certain length of time that algorithms may need to do something. The running time of computer algorithms is dependent on how big the problem is, and the size of problems is always changeable. For instance, if you're computing something using a list of numbers, the time to run the algorithm can increase dramatically if you add more numbers to the list, or it may not increase much at all. Because of the fickle nature of computing problems, it is useful to determine the running time of algorithms using a variable to represent the size of the problem.

So, if there're n elements in our list of numbers, then an algorithm that runs in polynomial time would have its running time expressed as something like Cn, where C is the number of steps it takes to process each node. The running time is stil within the bounds of polynomial time as long as the formula fits the form cnx(x-1) + ... + cn0, where c and x are constants. This is more easily expressed as O(nx). (See Big-oh notation)

An example of a non-polynomial time algorithm would have a running time like O(n!). (See factorial)

Log in or register to write something here or to contact authors.