Asymptotic Functions

Share this: Google+
< Contents | Previous | Next >

If you want to read a little bit more technical, this page is for you, otherwise you may skip to the next page.

What is the meaning of asymptotic function for algorithm complexity?

In one word, it would be dominant. We are looking for dominant behavior of the function. The concern of the asymptotic function is the behavior of the function on how quickly it grows when its input n grows really big. It ignores the behavior for small values of n.

Basically there are three fundamental type of functions that we often used for algorithm complexity:

Exponential: grow very quickly

Examples:

Polynomial: grow normally

Example:

Logarithmic: grow very slowly

Example:

Algorithm that runs at exponential is infeasible because it grows very quickly.

Exponential function is dominant over polynomial function.
Example: is considered as exponential function.

Polynomial function is dominant over logarithm function.
Example: is considered as polynomial function.

If we put them together with real constants we will have more general asymptotic function as proposed by Jeff Edmond in How to think about algorithm:

Examples:

If we have exponential function
If we have polynomial function
If we have logarithmic function

Note that

Factorial function can also be approximated as
If then we always have exponential function regardless the values of because exponential function is dominant over polynomial and over logarithmic function.
If and then we have polynomial function because polynomial is dominant over logarithmic function.