List of Common Function Orders
Reading Time: 1 minute
The table lists the most common orders of functions that are found in many day-to-day algorithms.
| Notation | Name | Well Known Example |
|---|---|---|
| $Θ(1)$ | Constant | Access time of an array element |
| $Θ(\log n)$ | Logarithmic | Worst case running time of binary search algorithm |
| $Θ(n)$ | Linear | Worst case running time of linear search algorithm |
| $Θ(n \log n)$ | Quasilinear | Lower bound time of any comparison-based sorting |
| $Θ(n^2)$ | Quadratic | Worst case running time of quicksort, insertion sort |
| $Θ(n^2 \log n)$ | Quasiquadratic | - |
| $Θ(n^3)$ | Cubic | - |
| $Θ(2^n)$ | Exponential | - |
| $Θ(n!)$ | Factorial | Solving travelling salesman problem via brute-force |