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(n^{2}) |
Quadratic |

O(n^{3}) |
Cubic |

O(2^{n}) |
Exponential |

**Comparing the growth of polynomial functions**:

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

**Comparing the growth of linear, quadratic and cubic**:

Note here that for n > 1, n = O(n^{2}) and n^{2} = O(n^{3}) (in other words, n is upper-bounded by n^{2} and n^{2} is upper-bounded by n^{3}).

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

**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).

**Comparing the growth of n log(n) and n ^{2}**:

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

**Comparing the growth of n ^{2} and 2^{n}**:

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