An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(nk) for some constant k. Problems for which a polynomial time algorithm exists belong to the complexity class P, which is central in the field of computational complexity theory. Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".
Some examples of polynomial time algorithms:
- The quicksort sorting algorithm on n integers performs at most operations for some constant A. Thus it runs in time and is a polynomial time algorithm.
- All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
- Maximum matchings in graphs can be found in polynomial time.
Read more about this topic: Time Complexity
Famous quotes containing the word time:
“In time of war you know much more what children feel than in time of peace, not that children feel more but you have to know more about what they feel. In time of peace what children feel concerns the lives of children as children but in time of war there is a mingling there is not children’s lives and grown up lives there is just lives and so quite naturally you have to know what children feel.”
—Gertrude Stein (1874–1946)