For example, 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 is of great practical importance.
Since Big O notation essentially captures how well an algorithm scales, subquadratic algorithms scale to higher problem sizes much better than algorithms of quadratic or higher complexity. For example, say we have two algorithms (call them A and B) which compute a function . Algorithm A computes in steps, rounded up, (making it an algorithm, and algorithm B comptutes it in steps, making it a quadratic () algorithm.
In this case, algorithm B outperforms algorithm A for all integer values of . On the other hand, for , the quadratic algorithm is doing more work than the algorithm, and the difference becomes even more dramatic for higher values of . By the time , the quadratic algorithm is doing almost times the work of the subquadratic algorithm.
See also: Big O notation