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 |