Big-O
- Analysis of an algorithm's efficiency
- Rate of growth of operations
- How the runtime or space increases as the input increases
- Big-O is a measurement of the worst case
Rules
- Ignore constants
- Values that don't scale with the input
- Ignore low-order terms
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 |