< Contents | Previous | Next >

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.