# Big O

- Expresses computing time as the term in a function that increases most rapidly to the size of a problem
- How fast an algorithm is
- Rate of growth of operations
- How the running time will increase as the input increases

- Worst-case run time
*Can we do better?*

## Common Run Times

- Fastest --> slowest

Big O | Name |
---|---|

$O(1)$ | constant/bounded time |

$O(log ; n)$ | log time |

$O(n)$ | linear time |

$O(n ; log ; n)$ | $n ; log ; n$ time |

$O(n^2)$ | quadratic/exponential time |

$O(2^n)$ | exponential time |

$O(n!)$ | factorial time |