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 greatest waste of time he knew of was to count the hours—what good can come of it?—and the greatest illusion in the world, to lead one’s day by the sound of the clock, and not by precepts of common sense and understanding.”
—François Rabelais (1494–1553)