Asymptotic complexity

From DmWiki

For algorithms which take an input of varying size (for instance, algorithms that operate on a list of n elements), the algorithm's asymptotic complexity is a measure of how strongly or weakly the amount of time needed to finish the algorithm depends on the size n of the input. The notation used to describe asymptotic complexity is called "big-O notation".

For instance:

• A function is O(1) or constant-time if it always takes the same amount of time regardless of n.
• A function is O(n) or linear-time if doubling n doubles the time required.
• A function is O(n²) or quadratic-time if doubling n quadruples the time reqired.
• A function is O(logn) or logarithmic-time if squaring n doubles the time required.

The notation does not distinguish constants. Therefore, O(2n) = O(n), and O(n + 1) = O(n). Only the largest term contributes asymptotically, so O(n² + n) = O(n²), because n² > n when n is large. To be technical, to say that a function is O(f(n)) means that the time taken by the function is less than some constant times f(n). So the O-notation describes an upper bound on the execution time.

For more information, see Wikipedia: Big O notation (http://en.wikipedia.org/wiki/Big_O_notation).

This article is a stub. You can help improve the article by expanding it.