Big-O Complexity Reference
Common time complexities, from O(1) to O(n!), with examples and a growth chart.
Ordered fastest → slowest growth. Lower on the list means it scales worse as the input grows.
At n = 10 the curves already fan out: O(1) stays at 1, O(log n) ≈ 3, O(n) = 10, O(n log n) ≈ 33, and O(n²) = 100. The steeper the curve, the worse it scales.
Big-O notation describes how an algorithm’s running time (or memory) grows as the input size n grows, ignoring constants and lower-order terms. From best to worst the common classes are O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), and O(n!) — lower means it scales better.
What Big-O really tells you
Big-O is a way to talk about how an algorithm behaves as the input gets large, not how many milliseconds it takes on your laptop. It captures the shape of the growth — flat, linear, quadratic, exponential — while deliberately throwing away constant factors and slower-growing terms. That is why 3n + 7 and 500n are both just O(n): as n heads toward infinity, only the dominant term matters.
Reading the table and chart
The list above is ordered from fastest-growing to slowest-scaling. O(1) and O(log n) are the classes you hope for; O(n) and O(n log n) are the workhorses of good algorithms; O(n²) and worse become painful as data grows. The chart plots the first five classes for n up to 10 so you can see the curves fan apart — O(1) stays flat while O(n²) climbs steeply.
Common time complexities, fastest → slowest
Ordered by how quickly the operation count grows with n. Lower on the list scales worse.
| Notation | Name | Typical example | Scales |
|---|---|---|---|
| O(1) | Constant | Array index, hash lookup | Excellent |
| O(log n) | Logarithmic | Binary search | Excellent |
| O(n) | Linear | Single loop, linear search | Good |
| O(n log n) | Linearithmic | Merge sort, heap sort, efficient sorts | Good |
| O(n²) | Quadratic | Nested loops, bubble / insertion sort | Fair |
| O(n³) | Cubic | Naïve matrix multiply, triple loop | Poor |
| O(2ⁿ) | Exponential | Recursive Fibonacci, subset enumeration | Bad |
| O(n!) | Factorial | Brute-force travelling salesman, permutations | Terrible |
How to use it well
Big-O by convention describes the worst-case asymptotic growth: the behaviour as n → ∞, for the least favourable input. Constants and lower-order terms are dropped, so O(n) beats O(n²) for large n even if the O(n²) routine wins on tiny inputs. When two algorithms share the same class, Big-O cannot separate them — you then compare constants, memory, and real benchmarks. As a rule of thumb, lower on the list above is better, and moving from O(n²) to O(n log n) is often the single biggest win available.