Big O notations
Commonly-used notations in the theory of algorithms
| notation | example | provides | shorthand for | used to |
|---|---|---|---|---|
| Big Theta | \( \Theta (N^2) \) | asymptotic order of growth | \( {1 \over 2} \ N^2 \) \( 10 \ N^2 \) \( 5 N^2 + 2 N \log N + 3 N \) | classify algorithms |
| Big Oh | \( O (N^2) \) | \(\Theta(N^2) \) and smaller | \( 10 \ N^2 \) \( 100 \ N \) \( 2 N \log N + 3 N \) | develop upper bounds |
| Big Omega | \( \Omega (N^2) \) | \( \Theta(N^2) \) and larger | \( {1 \over 2} \ N^2 \) \( N^5 \) \( N^3 + 2 N \log N + 3 N \) | develop lower bounds |
| Tilde * | \( \sim 10 \ N^2 \) | leading term | \( 10 \ N^2 \) \( 10 \ N^2 + 22 N \log N \) \( 10 \ N^2 + 2 N + 37 \) | provide approximate model |
* A common mistake is interpreting Big-Oh as an approximate model Tilde.
