# 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.

Concept · Algorithms & complexity · https://levelcode.org/concepts/big-o-notation

**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.Contains` or `Array.prototype.includes` inside 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](https://levelcode.org/roadmaps/software-engineer/algorithms) applies it to real code, and [latency numbers](https://levelcode.org/concepts/latency-numbers) put constants back in.