f(n) | Name | Example |

1 | Constant | + |

log(n) | Logarithmic | binary search |

log ^{2}(n) | Log-squared | |

n | Linear | max of array |

n*log(n) | Linearithmic | quicksort |

n ^{2} | Quadratic | selection sort |

n ^{3} | Cubic | matrix multiply |

n ^{k} | Polynomial | |

2 ^{n} | Exponential | knapsack problem |

When we use *log(n)*, we often mean *log _{2}(n)*; however, the
base of the