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
- Polynomial: grow normally
- Logarithmic: grow very slowly
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:
- If we have exponential function
- If we have polynomial function
- If we have logarithmic function
- 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.
If and then
How to cite this tutorial:
Teknomo, Kardi. (2017) Analysis of Algorithm .