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:
“We New Yorkers see more death and violence than most soldiers do, grow a thick chitin on our backs, grimace like a rat and learn to do a disappearing act. Long ago we outgrew the need to be blowhards about our masculinity; we leave that to the Alaskans and Texans, who have more time for it.”
—Edward Hoagland (b. 1932)