Big-O Notation Explained With Real Code Examples
Big-O notation describes how an algorithm's cost grows as input grows. Learn the common classes, how to read them, and the mistakes beginners make.
By Velloreth
What Big-O notation actually measures
Big-O notation describes how the cost of an algorithm grows as its input grows. It is not a stopwatch. It does not tell you how many milliseconds something takes. It tells you the shape of the relationship between input size and work done.
That distinction matters because it is what makes Big-O useful. A measurement in milliseconds is true only for one machine, one language, and one input. A growth rate is true everywhere.
Formally, we say an algorithm is O(f(n)) if there exist constants c and n₀ such that for all n greater than n₀, the running time is at most c × f(n). In practice you never compute those constants. You read the code, count how the work scales, and drop everything except the fastest-growing term.
The common complexity classes
These are the classes you will meet in real code, ordered from best to worst.
| Class | Name | Doubling n multiplies work by | Typical source |
|---|---|---|---|
| O(1) | Constant | 1× (unchanged) | Array index, hash lookup |
| O(log n) | Logarithmic | ~1× plus a constant | Binary search, balanced tree |
| O(n) | Linear | 2× | Single pass over a list |
| O(n log n) | Linearithmic | ~2× plus a bit | Efficient sorting |
| O(n²) | Quadratic | 4× | Nested loops over the same input |
| O(2ⁿ) | Exponential | Squared | Naive subset enumeration |
The gap between these is not academic. At n = 1,000,000, an O(n log n) sort does roughly 20 million operations while an O(n²) sort does a trillion. That is the difference between a page that loads and a page that times out.
Reading complexity from code
The skill is recognising which part of your code scales with the input.
Constant time: O(1)
function firstItem(items) {
return items[0];
}
No matter how long items is, this does one thing. Array indexing is O(1) because the element’s address is computed directly from the index.
Hash map lookups are also O(1) on average:
const seen = new Map();
seen.set('key', 1);
seen.get('key'); // O(1) average
The “average” qualifier matters. A hash map degrades to O(n) per lookup in the worst case when many keys collide, which is why a good hash function and a sensible load factor matter.
Linear time: O(n)
function sum(numbers) {
let total = 0;
for (const n of numbers) total += n;
return total;
}
One pass, one operation per element. Double the array, double the work.
Quadratic time: O(n²)
function hasDuplicatePairs(items) {
for (let i = 0; i < items.length; i++) {
for (let j = i + 1; j < items.length; j++) {
if (items[i] === items[j]) return true;
}
}
return false;
}
The outer loop runs n times, and for each iteration the inner loop runs roughly n times. That is n × n = n².
The same problem in O(n) with a set:
function hasDuplicatePairs(items) {
const seen = new Set();
for (const item of items) {
if (seen.has(item)) return true;
seen.add(item);
}
return false;
}
This is the single most common performance win available to a working developer: replacing a nested loop with a hash-based lookup.
Logarithmic time: O(log n)
function binarySearch(sorted, target) {
let low = 0;
let high = sorted.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (sorted[mid] === target) return mid;
if (sorted[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
Each iteration halves the search space. Starting from a million elements, you reach one in about 20 steps, because 2²⁰ ≈ 1,000,000. That is what makes binary search so much better than scanning.
The mistakes beginners make
Assuming nested loops always mean O(n²). They mean O(n²) only when both loops scale with the same input. This is O(n):
for (const word of words) {
for (const letter of 'abcdefghijklmnopqrstuvwxyz') {
// 26 iterations, always
}
}
The inner loop is bounded by a constant, so it collapses into the outer loop’s cost.
Forgetting that built-in methods have costs. Array.prototype.includes is O(n). Calling it inside a loop gives you O(n²) without a single nested for:
// O(n²) — includes() scans the array every time
for (const id of ids) {
if (otherIds.includes(id)) { /* ... */ }
}
// O(n) — one set, then constant-time lookups
const otherSet = new Set(otherIds);
for (const id of ids) {
if (otherSet.has(id)) { /* ... */ }
}
Confusing time and space. Big-O applies to memory too. A function that builds a set of every element is O(n) space. That is usually a fine trade, but it is a trade, and on a memory-constrained device it can be the wrong one.
Optimising the wrong thing. Big-O describes asymptotic behaviour. If your input is always 20 items, an O(n²) algorithm is not your problem — your problem is the network request, the database query, or the render. Measure before you rewrite.
Amortised complexity
Some operations are occasionally expensive but cheap on average. Appending to a dynamic array is the classic case.
const arr = [];
for (let i = 0; i < 1_000_000; i++) arr.push(i);
Most push calls are O(1). But when the array’s capacity is exhausted, the runtime allocates a larger block and copies everything over — an O(n) operation. Because the capacity doubles each time, those expensive copies happen at exponentially increasing intervals, and the total cost across n appends works out to O(n). So each append is O(1) amortised.
This is why push is not a performance concern, and why the same reasoning makes hash map insertion O(1) amortised.
How to use this in practice
You do not need to annotate every function. You need to notice the cases where growth will bite:
- Loops inside loops over the same collection — the classic quadratic trap.
- Linear scans inside loops —
includes,indexOf,findon arrays. - Repeated work that could be cached — recomputing the same value per iteration.
- Recursion without memoisation — naive Fibonacci is O(2ⁿ); with memoisation it is O(n).
When you find one, the fix is usually a hash map or set, a sort plus a single pass, or a cache. Those three moves resolve the large majority of real-world complexity problems.
If you want to go deeper on the structures that make these trade-offs possible, data structures every developer should know covers the practical set, and time vs space complexity explains the trade-off you are actually making. For the recursive case specifically, understanding recursion with practical examples walks through why naive recursion explodes and how memoisation fixes it.
Quotable summary
Big-O notation describes the growth rate of an algorithm’s cost as input size increases, discarding constant factors and lower-order terms. The classes you meet in practice, from best to worst, are O(1), O(log n), O(n), O(n log n), O(n²), and O(2ⁿ). Nested loops over the same input produce O(n²); replacing them with a hash-based lookup usually produces O(n). Big-O is a property of the algorithm, not the machine, which is why it is the right tool for reasoning about scale — and the wrong tool for reasoning about small inputs, where constants dominate.