Concept · Algorithms & complexity
Big-O notation
Describe how an algorithm's time or memory grows with input size, ignoring constants, so you can compare approaches before running them.
Big-O notation describes how the cost of an algorithm — time or memory — grows as its input grows. It keeps only the fastest-growing term and drops constant factors, so 3n² + 10n + 7 steps is simply O(n²). It answers "what happens when the input is 100 times bigger?", not "how many milliseconds will this take?".
The common classes
| Class | n = 1,000 | n = 1,000,000 | Typical source |
|---|---|---|---|
| O(1) | 1 | 1 | array index, hash-map lookup |
| O(log n) | ~10 | ~20 | binary search, balanced-tree lookup |
| O(n) | 1,000 | 1,000,000 | one pass over the input |
| O(n log n) | ~10,000 | ~20,000,000 | efficient sorting |
| O(n²) | 1,000,000 | 10¹² | nested loops over the input |
| O(2ⁿ) | astronomical | astronomical | trying every subset |
Working it out
- Sequential steps add, and the biggest term wins: an O(n) scan then an O(n log n) sort is O(n log n).
- Nested loops multiply: a loop over n items containing a loop over n items is O(n²) — including hidden loops such as
slices.ContainsorArray.prototype.includesinside a loop. - Halving the problem each step gives O(log n).
- Space complexity counts extra memory, including the recursion stack.
Say which case you mean. Hash-map lookups are O(1) on average but O(n) in the pathological worst case; quicksort averages O(n log n) and can degrade to O(n²). Amortized cost spreads occasional expensive operations over many cheap ones — appending to a dynamic array is amortized O(1) even though a resize copies everything.
Where it misleads
Big-O ignores constants and memory layout, so for small inputs a "worse" algorithm often wins: a linear scan of 20 contiguous integers beats a hash lookup, and insertion sort beats merge sort on tiny arrays (which is why real sort implementations switch to it). Use Big-O to rule out approaches that can't scale, then measure. The algorithms lesson applies it to real code, and latency numbers put constants back in.