1

From here, I know it is that an algorithm that...

...is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^k) for some nonnegative integer k, where n is the complexity of the input.

Can some of you offer examples involving common data structures to explain polynomial time? I've looked it up but the available information is scarce.

1
  • 2
    Related: stackoverflow.com/questions/487258/… . And to "available information is scarce" - there is actually so much information about this topic available, that you probably missed to see the wood for the trees. "Computational complexity theory" is a complete branch of theoretical computer science dealing with these things, and there are at least thousands of papers and books written about it.
    – Doc Brown
    Feb 4, 2015 at 1:34

4 Answers 4

2

What "polynomial time" means is that if you calculate a formula describing how long the algorithm will take to complete on a data set with n elements, the largest-magnitude term in the formula will be in the form of n^x.

Here are a few examples of runtime classes:

  • O(1): the runtime does not get larger as the data set increases in size. Example: Array access. Retrieving an arbitrary element in an array happens just as fast no matter how big the array is. (Theoretically. In practice, if the array overflows physical memory and has to be paged to disc, that can change, but the complexity theory doesn't concern itself with details like that.)
  • O(log n): the runtime increases as the log of the size of the data set, a number which grows more slowly than the data set itself. Example: A binary search through an array or balanced tree. Since each check cuts the remaining number of elements under consideration in half, it will take 2 checks to search through 3 elements, 3 checks to search 7 elements, 4 checks to search 15 elements... and so on. With 32 checks, you can search over 4 billion elements by a binary search.
  • O(n): The runtime increases at a rate directly proportionate to the size of the dataset. Example: A linear search through an array. It will take 10 checks to iterate over 10 elements, or 4 billion checks to iterate over 4 billion elements.
  • O(n log n): The runtime increases faster than the size of the dataset, at a rate proportionate to the size times the log of the size. Example: divide-and-conquer sorting algorithms such as Quicksort and Mergesort, where the values to be searched get divided into smaller and smaller groups, much like the binary search above.
  • O(n^2): This is polynomial time, where the runtime increases proportionate to the square of the data set. Any class where the runtime increases based on n^x, for any value of x, is considered polynomial time. Example: Linear sorting algorithms where the values to be searched do not get divided into smaller groups, such as Bubble Sort and Insertion Sort. In order to find where each element belongs, the algorithm must search the entire array, so the general runtime is n (the number of elements) times n (the number of elements to search through for each element). The actual runtime will be lower, as you won't have to search the entire array for every single element, but complexity theory deals with generalizations, and in practice the amount of searching you end up not doing won't be enough to compensate for the increased complexity that comes with increasing size.

Polynomial time is important, because it's considered the highest class that is still "fast" by complexity theory. There are higher complexity classes where complexity becomes very unmanageable very quickly, and they comprise some of the more interesting questions in computer science and information theory.

For example, the Travelling Salesman Problem, which can determine the most efficient order in which to perform a series of tasks, takes exponential time to solve: O(2^n). This is very different from O(n^2); 32^2 = 1024, but 2^32 is over 4 billion, which explains why the complexity of NP algorithms (Non-deterministic Polynomial-time, or algorithms not known to have a solution that runs in polynomial-time or better) explodes once you get past trivial data sets!

1

One of the most common ways to express polynomial time, O(nk), is nested loops where n is used as an input to calculate the maximum iterations of each loop and k is the level of nested loops.

For example, this loop is O(n2) because it is a doubly-nested loop where n is the number of iterations:

int n = ...;
int x = 0;
for (int i = 0; i < n; ++i) {
  for (int i = j; j < n; ++j) {
    ++x;
  }
}

If you add a third loop it would be O(n3).

1

Consider finding the smallest element in an unsorted collection. While you could use an array or linked list to hold the data, the time complexity will be O(n) as each element has to be examined as that could be the smallest that hasn't been known yet.

1

A classic example of an O(n³) algorithm is matrix multiplication. Multiplying two 10x10 matrices together will require 10^3 multiplications.

In practice, however, modern algorithms such as the Coppersmith–Winograd algorithm can bring the order down to about 2.37.

2
  • Although, Coppersmith–Winograd is hardly of practical use!
    – Rufflewind
    Feb 4, 2015 at 0:42
  • Well, technically, matrix multiplication is O(n^1.5). It's not appropriate to use the dimension of the matrix as n. You should be using the number of elements as n. That having been said, matrix multiplication often arises when a problem of size n is solved by creating n×n arrays and performing operations (multiplication, inversion, etc.) on those arrays.
    – ganbustein
    Feb 4, 2015 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.