Big O notation gets taught with more math notation than it needs. Here's the practical version.
What it actually measures
Big O describes how an algorithm's runtime (or memory) grows as the input size grows — not the actual speed in seconds. It answers one question: "if I double the input, roughly how much worse does this get?"
The complexities you'll actually see
| Notation | Name | Doubling the input... | Example |
|---|---|---|---|
| O(1) | Constant | ...changes nothing | Array index access |
| O(log n) | Logarithmic | ...adds one step | Binary search |
| O(n) | Linear | ...doubles the work | A single loop through an array |
| O(n log n) | Linearithmic | ...slightly more than doubles | Efficient sorting (merge sort, quicksort) |
| O(n²) | Quadratic | ...quadruples the work | Nested loops over the same data |
| O(2ⁿ) | Exponential | ...squares the work | Naive recursive Fibonacci |
Spotting complexity in your own code
// O(n) — one pass
function sum(arr) {
let total = 0;
for (const n of arr) total += n;
return total;
}
// O(n²) — nested loop over the same input
function hasDuplicate(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true;
}
}
return false;
}The second function re-scans the array for every element — that nested "loop inside a loop over the same data" pattern is the most common way O(n²) sneaks into real code.
The fix is usually a hash map
// O(n) — trade memory for speed
function hasDuplicate(arr) {
const seen = new Set();
for (const n of arr) {
if (seen.has(n)) return true;
seen.add(n);
}
return false;
}Swapping an inner loop for a Set or Map lookup (O(1) average case) is the single most common optimization you'll make in practice — it turns O(n²) into O(n) at the cost of extra memory.
When it doesn't matter
For a list of 20 items, O(n²) vs O(n) is invisible to a user — both run in microseconds. Big O matters when n gets large or runs frequently (hot paths, data processing, anything operating on user-generated collections that can grow unbounded). Don't reach for cleverness on code that will only ever touch a handful of items — readability wins until the data proves otherwise.
