Added to Favorites

Popular Searches

Definitions

Nearby Words

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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday August 25, 2008 at 16:45:28 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday August 25, 2008 at 16:45:28 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.