Big O Notation Without the Math Panic

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

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.

Space complexity, briefly

Everything above describes time complexity — how runtime grows. The same notation describes memory too, and the two often trade against each other, as in the hasDuplicate example: the O(n) time version uses a Set that grows with the input (O(n) space), while the original O(n²) nested-loop version uses no extra memory at all (O(1) space). Neither is universally "better" — for a memory-constrained environment processing huge inputs, the slower, no-extra-memory version might genuinely be the right choice, which is exactly why "faster" and "better" aren't the same question.

Best, worst, and average case

A single Big O figure can hide real variation depending on the input. Searching an unsorted array for a value is O(n) in the worst case (the value is last, or absent) — but that single number doesn't capture that the best case (the value is first) is O(1). Common algorithms are usually described by worst case unless stated otherwise, since that's the guarantee that actually matters for reliability — quicksort, for instance, averages O(n log n) but has an O(n²) worst case on already-sorted or adversarially-chosen input, which is exactly why some standard library sort implementations use a hybrid approach specifically to avoid that worst case in practice.

A five-minute mental checklist

Reasoning about complexity is one habit that separates code that merely works from code that holds up under real load — the same throughline running through clean code principles that actually hold up, where readability and correctness matter more than cleverness. And if your Big O intuition isn't panning out in a real measurement, Core Web Vitals is where that gap between theory and actual user-perceived performance gets measured concretely.

Common mistakes

Related reading

• Clean Code Principles That Actually Hold Up in Practice — shares tags: programming, productivity (same category).
• Python Virtual Environments: venv, pipenv, poetry, or uv? — shares tags: programming, productivity.
• Async Python with asyncio: A Practical Introduction — shares tags: programming.
• Understanding Cloud Cost Optimization Basics — shares tags: productivity.
• Core Web Vitals Explained: What Actually Affects Your Score — shares tags: programming.