Growth of functions

In algorithmic analysis, we learn to characterize the complexity in terms of an upper bound (Big-oh), a lower bound (Big-omega) and an order function (Big-theta). Here are the definitions:

1. Upper bound function (i.e., T(n) is upper-bounded by f(n)): We say,

T(n) = O(f(n)) iff

there exist constants c, N > 0, such that T(n) ≤ c f(n) for all n > N.

2. Lower bound function (i.e., T(n) is lower-bounded by f(n)): We say,

T(n) = Ω(f(n)) iff

there exist constants c, N > 0, such that T(n) ≥ c f(n) for all n > N.

3. Order function (i.e., T(n) is of the order of f(n)): We say,

T(n) = Θ(f(n)) iff

there exist constants c1, c2, N > 0, such that c1 f(n)T(n) ≤ c2 f(n) for all n > N.

A deep understanding of the asymptotic complexities involves getting a good sense of how different growth functions behave as n approaches infinity. In this article, we present a  visualization of the growth of commonly occurring functions.

Here is a summary of the common functions in the increasing order of complexity:

T(n) Nomenclature
O(1) Constant
O(log n) Logarithmic
O(n) Linear
O(n log n) n-log-n
O(n2) Quadratic
O(n3) Cubic
O(2n) Exponential

Comparing the growth of polynomial functions:

Note that the higher order polynomial functions grow much slower in the beginning till (n = 1).

comparePolynomials

Comparing the growth of linear, quadratic and cubic:

Note here that for n > 1, n = O(n2) and n2 = O(n3) (in other words, n is upper-bounded by n2 and n2 is upper-bounded by n3).

Since lower-bound function is a converse of upper-bound function, we can also say, for n > 1, n2 = Ω(n) and n3 = Ω(n2) (in other words, n2 is lower-bounded by n and n3 is lower-bounded by n2).

compareLinearQuadraticCubic

Comparing the growth of logarithmic with linear:

Here, we can say that for any n > 1, log(n) = O(n) (or, log(n) is upper-bounded by n).

compareLogLinear

Comparing the growth of n log(n) and n2:

Here, we can say that for any n > 1, n log(n) = O(n2) (or, n log(n) is upper-bounded by n2).

compareNlogNQuadratic

Comparing the growth of n2 and 2n:

Here, we can say that for any n > 1, n2 = O(2n) (or, n2 is upper-bounded by 2n).

compareQuadraticExponential

 

This entry was posted in Data-structures. Bookmark the permalink.

Comments are closed.