[Overview] [Previous] [Next]

# Polynomial-Time Algorithms

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(n2) time. Bubble sort takes linear time in the best case, but O(n2) 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(n2) 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 n2, 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.