Subquadratic time

Subquadratic time

In computing an algorithm is said to run in subquadratic time if its running time f(n) is less then o(n^2).

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 O(nln n) 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 f(n). Algorithm A computes f in 10n log_2(n) + 3n + 4 steps, rounded up, (making it an O(n log (n)) algorithm, and algorithm B comptutes it in n^2 + 2n + 1 steps, making it a quadratic (O(n^2)) algorithm.

In this case, algorithm B outperforms algorithm A for all integer values of n < 61. On the other hand, for n=100, the quadratic algorithm is doing 46% more work than the O(n log (n)) algorithm, and the difference becomes even more dramatic for higher values of n. By the time n=1000, the quadratic algorithm is doing almost 10 times the work of the subquadratic algorithm.

See also: Big O notation

Search another word or see Subquadratic timeon Dictionary | Thesaurus |Spanish
Copyright © 2014, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature