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:
“The chuck wagon carries the food and utensils for the range kitchen. Man-at-the-pot is the first buckaroo to pick up the coffee pot when out with the chuck wagons. It becomes his duty to pour the coffee for the outfit. “Come and get her before I throw her out” is the time honored mess call.”
—Administration in the State of Neva, U.S. public relief program (1935-1943)