Sub-quadratic time
An algorithm is said to be subquadratic time if T(n) = o(n2).
For example, simple, 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.
Comments
Post a Comment