Skip to content

Polynomial time

As a high school refresher, in mathematics, a polynomial is an expression that involves a sum of terms, where each term is a constant multiplied by a variable raised to a non-negative integer power. For example:

  • 3x^2 + 2x + 1 is a polynomial with three terms: 3x^2, 2x, and 1.
  • x^3 + 4x^2 + x + 7 is another polynomial with four terms.

When we say a problem can be solved in polynomial time, we are talking about how the time it takes to solve the problem depends on the size of the input.

  • Input size: This is how big the problem is. For example, if you’re sorting a list of numbers, the input size is the number of elements in the list.
  • Polynomial time: This means that the amount of time a computer takes to solve the problem increases at a rate proportional to a polynomial function of the input size. In simpler terms, if the input size is n, then the time to solve the problem might grow like n^2, n^3, or even just n, but it doesn’t grow too quickly.

For example:

  • If a sorting algorithm runs in O(n^2) time, that means if you double the number of elements to be sorted, the time it takes to sort them might quadruple.
  • If an algorithm runs in O(n) time, that means the time to solve the problem grows linearly with the input size (double the input, double the time).

Non-polynomial time

In contrast, exponential time grows much faster. For example, 2^n grows much more quickly than n^2 as n increases. For instance:

  • For n = 10, n^2 = 100, while 2^n = 1024.
  • For n = 20, n^2 = 400, but 2^n = 1,048,576.

In many computational problems (especially NP-complete problems), we suspect they require exponential time to solve, which is why they become intractable as the input size grows.

Why is polynomial time important?

Problems that can be solved in polynomial time are considered “tractable” or “efficient.” In practical terms, this means that for reasonable input sizes, a computer can solve them in a realistic amount of time. Many problems in computer science aim to find polynomial-time algorithms because exponential-time algorithms would take too long as the input grows.

Putting it simply

  • Polynomial time: The time to solve a problem grows in a manageable way as the input gets bigger (like n^2 or n^3).
  • Exponential time: The time grows way too fast (like 2^n or 3^n) as the input gets bigger.