Big-O notation explained
Big-O notation describes how the work of an algorithm grows as its input grows. It ignores constants and small terms and keeps only the part that dominates for large inputs, so it tells you which algorithm will keep up when the data gets big.
See the growth
Move the slider. The curves that leave the chart are the ones that stop being practical.
- O(1)Constant
- O(log n)Logarithmic
- O(n)Linear
- O(n log n)Linearithmic
- O(n²)Quadratic
- O(2ⁿ)Exponential
| Growth | Operations for n = 16 |
|---|---|
| O(1) Constant | 1 |
| O(log n) Logarithmic | 4 |
| O(n) Linear | 16 |
| O(n log n) Linearithmic | 64 |
| O(n²) Quadratic | 256 |
| O(2ⁿ) Exponential | 65,536 |
What it means in time
Assuming a computer that does a billion simple operations per second. Real programs are slower, but the proportions are the same.
| Growth | n = 1,000 | n = 1,000,000 |
|---|---|---|
| O(log n) | under a millisecond | under a millisecond |
| O(n) | under a millisecond | 1 milliseconds |
| O(n log n) | under a millisecond | 20 milliseconds |
| O(n²) | 1 milliseconds | 17 minutes |
Where each one shows up
O(1) Constant: the work does not depend on n.
Reading array[i]
O(log n) Logarithmic: halve the problem each step.
O(n) Linear: look at every element once.
O(n log n) Linearithmic: split in halves, do linear work at each level.
O(n²) Quadratic: compare every element with every other.
Bubble sort, Selection sort, Insertion sort, Dijkstra's algorithm
Rules of thumb
- Drop constants. Doing twice the work is still linear: O(2n) is O(n).
- Keep the dominant term. n² + n is O(n²), because n² wins for large n.
- Nested loops multiply. A loop over n inside a loop over n is O(n²).
- Halving means a logarithm. Cutting the problem in half each step takes about log n steps.
- Say which case you mean. Best, average and worst can differ a lot: quick sort is O(n log n) on average and O(n²) in the worst case.
The algorithms in the path
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) | O(1) |
| Binary search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Breadth-first search | O(V + E) | O(V + E) | O(V + E) | O(V) |
| Depth-first search | O(V + E) | O(V + E) | O(V + E) | O(V) |
| Dijkstra's algorithm | O(V²) | O(V²) | O(V²) | O(V) |
| Stack | O(1) | O(1) | O(1) | O(n) |
| Queue | O(1) | O(1) | O(1) | O(n) |
| Binary search tree | O(1) | O(log n) | O(n) | O(n) |
| Binary heap | O(1) | O(log n) | O(log n) | O(n) |
| Linked list | O(1) | O(n) | O(n) | O(n) |
| Hash table | O(1) | O(1) | O(n) | O(n) |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) |
| Radix sort | O(d (n + k)) | O(d (n + k)) | O(d (n + k)) | O(n + k) |
V is the number of nodes and E the number of edges. Dijkstra is shown with the simple list used in its lesson; a heap makes it O((V + E) log V). For counting and radix sort, k is the number of possible values (or digit values) and d the number of digits; they compare no values.