Sub-quadratic Time
An algorithm is said to be subquadratic time if T(n) = o(n2).
For example, most naïve comparison-based sorting algorithms are quadratic (e.g. insertion sort), but more advanced algorithms can be found that are subquadratic (e.g. Shell sort). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.
Read more about this topic: Time Complexity
Famous quotes containing the word time:
“He that will not apply new remedies, must expect new evils: for Time is the greatest innovator: and if Time, of course, alter things to the worse, and wisdom and counsel shall not alter them to the better, what shall be the end?”
—Francis Bacon (1561–1626)
Related Phrases
Related Words