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:
“You say your own soul supplies you with some sort of an idea or image of God. But at the same time you acknowledge you have, properly speaking, no idea of your own soul. You even affirm that spirits are a sort of beings altogether different from ideas. Consequently that no idea can be like a spirit. We have therefore no idea of any spirit.”
—George Berkeley (1685–1753)