Big-O Complexity Reference
| Notation | Name | Typical operations / algorithms | n = 10 | n = 100 | n = 1000 |
|---|---|---|---|---|---|
| O(1) | Constant | Array index lookup, hash map get/set, arithmetic on fixed-size numbers | 1 | 1 | 1 |
| O(log n) | Logarithmic | Binary search, balanced binary search tree lookup | 3 | 7 | 10 |
| O(n) | Linear | Linear scan, array traversal, finding the max of an unsorted list | 10 | 100 | 1,000 |
| O(n log n) | Linearithmic (log-linear) | Merge sort, quicksort (average case), heapsort | 33 | 664 | 9,966 |
| O(n²) | Quadratic | Bubble sort, insertion sort, nested loops over the same input | 100 | 10,000 | 1,000,000 |
| O(n³) | Cubic | Naive matrix multiplication, triple-nested loops over the same input | 1,000 | 1,000,000 | 1,000,000,000 |
| O(2ⁿ) | Exponential | Naive recursive Fibonacci, enumerating every subset of a set | 1,024 | n/a (astronomical) | n/a (astronomical) |
| O(n!) | Factorial | Brute-force traveling salesman, generating every permutation | 3,628,800 | n/a (astronomical) | n/a (astronomical) |
How it works
This is a reference table, not a benchmark — the growth values are the exact
mathematical formula for each class evaluated at n = 10, 100 and 1000 (rounded to the
nearest whole number for the logarithmic classes), not a timing measurement of any
real algorithm. Type a notation (e.g. O(n²)) or part of a name (e.g.
quadratic) to filter the table; clear the box to see every class again.
Exponential and factorial growth become astronomically large almost immediately — by n = 100 both already dwarf the number of atoms in the observable universe — so those cells show "n/a (astronomical)" past a small cutoff instead of a meaningless wall of digits.