What Big O Actually Describes

Big O is a way to talk about how an algorithm scales. It answers: "if I 10x the input, what happens to runtime?" Not "how many milliseconds does this take" — that depends on the machine, the language, and a hundred other things. Big O ignores all of that and describes shape: linear, quadratic, logarithmic, exponential.

The reason this matters: an O(n²) algorithm with n=100 takes 10,000 operations. With n=1,000,000 it takes 1,000,000,000,000 — a trillion. The same algorithm goes from "instant" to "stops the universe" with one input bump. Knowing the shape lets you predict that without running it.

O(1) — Constant Time

Same time regardless of input size. Hash map lookups, array indexing, simple arithmetic.

function getFirst(arr) { return arr[0]; // O(1) — same speed for arr of 10 or 10 million
} const map = new Map();
map.set("key", "value");
map.get("key"); // O(1) average

O(log n) — Logarithmic

Each step cuts the problem in half. Binary search, balanced tree operations. Doubling the input adds one extra step — incredibly scalable.

function binarySearch(arr, target) { let lo = 0, hi = arr.length - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (arr[mid] === target) return mid; if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1;
}

O(n) — Linear

One pass through the data. Almost everything reasonable falls here.

function sum(arr) { let total = 0; for (const x of arr) total += x; // O(n) return total;
}

O(n log n) — Linearithmic

Sorting. Mergesort, heapsort, and most production sort implementations. As good as it gets for comparison-based sorts.

arr.sort((a, b) => a - b); // O(n log n)

O(n²) — Quadratic (The Common Bug)

Nested loops over the same input. Looks innocent. Kills production.

// Find duplicates — O(n²) version
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;
} // Same problem — O(n) with a Set
function hasDuplicateFast(arr) { const seen = new Set(); for (const x of arr) { if (seen.has(x)) return true; seen.add(x); } return false;
}

That second version is the single most common optimization in code review. Whenever you see a nested loop checking each element against the others, a hash map turns it linear.

O(2ⁿ) — Exponential

Naive recursive solutions to problems with overlapping subproblems. The classic example: naive Fibonacci.

function fib(n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); // O(2^n) — calls explode
} // Memoized — O(n)
const memo = new Map();
function fibFast(n) { if (n < 2) return n; if (memo.has(n)) return memo.get(n); const result = fibFast(n - 1) + fibFast(n - 2); memo.set(n, result); return result;
}

When Big O Actually Matters

Not every loop needs to be optimal. Three rules of thumb:

  • If n is bounded and small (config files, UI lists under 100 items) — don't think about it.
  • If n comes from user input or database results — always think about it. A user can paste a million rows.
  • If the algorithm runs in a hot path (request handlers, render loops) — measure first, then optimize.

Premature optimization wastes time. But shipping O(n²) code that only ever sees 10 items in dev and then meets 100,000 in production is the most common performance incident in software.

Space Complexity

Same notation, but for memory. arr.map(x => x * 2) is O(n) time AND O(n) space — it allocates a new array. arr.forEach(x => sum += x) is O(n) time but O(1) space. For small data both are fine; for streaming millions of records, the difference is whether your service stays up.

Practice Recognizing It

The fastest way to internalize Big O is to read code with it in mind. Pick any open-source utility, find a function that processes a collection, and ask: what's the complexity? Then check if a hash map or sort would improve it. After 50 of these, you'll spot O(n²) loops the way you spot syntax errors. Pair this with a structured DSA roadmap and the abstract notation becomes muscle memory.