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!