Subquadratic time

From Wikipedia, the free encyclopedia

An algorithm is said to run in subquadratic time if its running time f(n) is less then o(n²). Most naïve sorting algorithms are quadratic (e.g., insertion sort), but more advanced algorithms can be found that are subquadratic (e.g., merge sort). No general-purpose sorts run in linear time, but the change from quadratic to the common O(nlnn) is of great practical importance.

See also: Big O notation