I wish I had this table back in 1984 when I was trying to understand this stuff.
| Big O Notation | Name | Example(s) |
|---|---|---|
| O(1) | Constant | # Odd or Even number, # Look-up table (on average) |
| O(log n) | Logarithmic | # Finding element on sorted array with binary search |
| O(n) | Linear | # Find max element in unsorted array, # Duplicate elements in array with Hash Map |
| O(n log n) | Linearithmic | # Sorting elements in array with merge sort |
| O(n2) | Quadratic | # Duplicate elements in array (naïve), # Sorting array with bubble sort |
| O(n3) | Cubic | # 3 variables equation solver |
| O(2n) | Exponential | # Find all subsets |
| O(n!) | Factorial | # Find all permutations of a given set/string |
and I now can firmly feel the difference between polynomial and exponential well worth this example:
n = 10 | 100 | 1000
n^2 = 100 | 10000 | 1000000
k^n = k^10 | k^100 | k^1000
