A *polynomial-time algorithm* is an algorithm whose execution time is either given
by a polynomial on the size of the input, or can be bounded by such a polynomial. Problems
that can be solved by a polynomial-time algorithm are called *tractable* problems.

For example, most algorithms on arrays can use the array size, n, as the input size. To
find the largest element in an array requires a single pass through the array, so the
algorithm for doing this is O(n), or *linear time.*

Sorting algorithms usually require either O(n log n) or O(n^{2})
time. Bubble sort takes linear time in the best case, but O(n^{2}) time in the
average and worst cases. Heapsort takes O(n log n) time in all cases. Quicksort
takes O(n log n) time on average, but O(n^{2}) time in the worst case.

Regarding O(n log n) time, note that

- The base of the logarithms is irrelevant, since the difference is a constant factor, which we ignore; and
- Although n log n is not, strictly speaking, a polynomial, the size of
n log n is bounded by n
^{2}, which*is*a polynomial.

Probably all the programming tasks you are familiar with have polynomial-time
solutions. This is *not* because all practical problems have polynomial-time
solutions. Rather, it is because your courses and your day-to-day work have avoided
problems for which there is no known practical solution.

Copyright © 1996 by David Matuszek

Last modified Apr 23, 1996