Big O Notation, Explained with Real Code

Big O notation gets taught with abstract examples — sorting arrays of integers, searching balanced trees — and then quietly dropped once people start shipping actual features. That's a mistake: the same reasoning explains why a "simple" nested loop over your production data can take down a server once that data grows past a few thousand rows. Here's Big O grounded in code you'd actually write.

What Big O actually measures

Big O describes how an algorithm's running time (or memory use) grows as input size grows — not the exact time, which depends on your CPU, but the shape of the growth curve. "O(n)" means "roughly proportional to input size." "O(n²)" means "roughly proportional to input size squared." The constant factors and exact instruction counts are deliberately thrown away; what matters is what happens as n gets large.

This matters because constant factors stop mattering at scale, and growth rate is all that's left. An O(n²) algorithm that's faster than an O(n) one at n = 100 will always lose once n is large enough — it's not a question of if, only of where the crossover point is.

O(1): constant time

Looking up a value by key in a Map or object doesn't get slower as the map grows — hashing the key and jumping to its bucket takes the same number of steps whether there are 10 entries or 10 million.

function getUserById(usersById, id) {
  return usersById.get(id); // O(1), regardless of map size
}

O(n): linear time

Work grows in direct proportion to input size. A single pass over an array — searching for a value, summing it, transforming each element — is the classic case:

function findFirstAdmin(users) {
  for (const user of users) {
    if (user.role === 'admin') return user; // worst case: checks every user once
  }
  return null;
}

Double the array, double the worst-case work. That's linear, and for most everyday operations, it's perfectly fine.

O(n²): quadratic time — the one that quietly kills production

This is where real bugs live. Nesting a loop inside a loop over the same data multiplies the work:

// find duplicate emails - O(n²): for every user, scan every other user
function findDuplicateEmails(users) {
  const duplicates = [];
  for (let i = 0; i < users.length; i++) {
    for (let j = i + 1; j < users.length; j++) {
      if (users[i].email === users[j].email) {
        duplicates.push(users[i].email);
      }
    }
  }
  return duplicates;
}

At 100 users, that's ~5,000 comparisons — instant. At 100,000 users, it's ~5 billion — the kind of thing that works fine in a demo with test data and then times out the moment it hits real production volume. This exact pattern — an inner loop or inner .find()/.includes() call over data that grows with the outer loop — is the single most common accidental-quadratic bug in application code.

The fix is almost always trading memory for time: build a lookup structure once (O(n)), then do O(1) lookups inside a single loop (O(n) total) instead of O(n) lookups inside a loop (O(n²) total).

// same result, O(n): one pass to build a Set, one pass to check membership
function findDuplicateEmails(users) {
  const seen = new Set();
  const duplicates = new Set();
  for (const user of users) {
    if (seen.has(user.email)) {
      duplicates.add(user.email);
    }
    seen.add(user.email);
  }
  return [...duplicates];
}

Same output, and it stays fast as the input grows — this is the trade that a Map/Set almost always represents: pay some memory to turn an O(n) lookup into an O(1) one.

O(log n): logarithmic time

Work grows much more slowly than input size — each step eliminates a large fraction of what's left to search. Binary search over a sorted array is the canonical example: check the middle, discard half, repeat.

function binarySearch(sortedArr, target) {
  let low = 0;
  let high = sortedArr.length - 1;

  while (low <= high) {
    const mid = (low + high) >> 1;
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Searching a sorted array of 1,000,000 items takes at most ~20 comparisons, not 1,000,000 — that's the difference between O(log n) and O(n) in practice. This is also why database indexes (typically B-trees) make lookups on large tables fast: they turn what would be an O(n) table scan into an O(log n) tree traversal.

O(n log n): the sort-family complexity

Most efficient comparison-based sorting algorithms (merge sort, quicksort's average case, and what Array.prototype.sort uses under the hood in modern JS engines) run in O(n log n) — better than O(n²), and it's the theoretical floor for comparison-based sorting. If you find yourself writing a hand-rolled sort that's O(n²) (like naive bubble sort), just use the built-in sort — it's both faster and already correct.

Reading complexity out of your own code

A rough set of rules that covers most everyday cases:

• A single loop over n items: O(n).
• A loop nested inside another loop, both over roughly the same n: O(n²).
• Halving the search space each iteration (binary search, balanced tree descent): O(log n).
• Array methods like .includes(), .indexOf(), and .find() are each O(n) on their own — calling one inside a loop is exactly the nested-loop pattern above, just spelled differently. This is the most common place quadratic behavior hides in plain sight.

// looks like one loop, is actually O(n²): .includes() scans the array each call
function withoutDuplicates(items) {
  const result = [];
  for (const item of items) {
    if (!result.includes(item)) result.push(item); // O(n) call, inside an O(n) loop
  }
  return result;
}

// O(n): Set.has() is O(1), so the loop stays linear
function withoutDuplicatesFast(items) {
  return [...new Set(items)];
}

Takeaway

Big O isn't about shaving milliseconds off code that already runs fine — it's about knowing which patterns silently stop scaling. The specific thing worth training your eyes to spot is an O(n)-or-worse operation (.includes(), .find(), another loop) sitting inside a loop over the same growing collection. That single pattern accounts for most of the "this worked in dev and fell over in production" bugs you'll actually encounter.