**Constant**: A program whose running time’s order of growth is constant executes a fixed number of operations and its running time does not depend on *N*.

**Logarithmic**: A program whose running time’s order of growth is *logarithmic* is barely slower than *constant*. The base of the logarithm is not relevant with respect to the order of growth, so its order of growth is *log N*.

**Linear**: Programs that spend a constant amount of time processing each piece of input data, or that are based on a single *for* loop. Its running time is proportional to *N*.

**Linearithmic**: Programs whose running time for a problem of size *N* has order of growth *N log N*.

**Quadratic**: Programs whose running time has order of growth *N^2* has two nested *for* loops, used for some calculation involving all pairs of *N* elements.

**Cubic**: Programs whose running time has order of growth *N^3* has three nested *for* loops, used for some calculation involving all triples of *N* elements.

**Exponencial**: Exponencial algorithms are extremely slow and its order of growth is b^N for any constant *b > 1*.

order of growth | description | example | |
---|---|---|---|

constant | 1 | statement | add two numbers |

logarithmic | log N |
divide in half | binary search |

linear | N |
loop | find the maximum |

linearithmic | N log N |
divide and conquer | mergesort |

quadratic | N^2 |
double loop | check all pairs |

cubic | N^3 |
triple loop | check all triples |

exponential | 2^N |
exhaustive search | check all subsets |

*Note*: this is not a complete set, it only contains the most common classfications.