When O(n²) Becomes a Problem

It worked fine in dev. It worked fine in staging. Then the users table crossed some threshold nobody was watching, and an endpoint that used to respond instantly started timing out. Nine times out of ten, the postmortem finds a nested loop, or something shaped like one, that nobody thought twice about when it was written — because at the size it was written and tested at, there was nothing to notice.

This post is about that gap: exactly how fast O(n²) goes from invisible to catastrophic, a real before-and-after fix with real numbers, and — just as important — when O(n²) genuinely isn't worth touching. For what O(n²) means and what it looks like in code, see Big O Notation Explained with Real Examples; this post picks up from there and asks the question that actually matters day to day: at what size does this become a problem?

The running example

A signup form checks new email addresses against a list of ones already registered, to reject duplicates. It's a single loop, and it reads as O(n) at a glance:

function hasDuplicates(emails) {
  for (let i = 0; i < emails.length; i++) {
    if (emails.indexOf(emails[i]) !== i) return true; // scans the whole array, every time
  }
  return false;
}

It isn't O(n). indexOf is itself an O(n) scan, called once per element — O(n) calls to an O(n) operation is O(n²), the exact non-nested pattern covered in Big O Notation Explained with Real Examples. In a hundred-row dev fixture, that distinction is invisible. Here's what it looks like as the list actually grows, at a typical single-core throughput of 100 million operations per second (the same default Algorithm Runtime Estimator uses):

Every row here is the same function. Nothing about the code changed between the first row and the last — only n did. That's the entire danger of O(n²): the same line of code is completely fine right up until, at some size nobody explicitly chose, it isn't. 100 to 10,000 rows feels like a rounding error in testing. 10,000 to 1,000,000 is the difference between a millisecond and a support ticket.

Algorithm Runtime Estimator computes this exact table for any input size and any throughput you plug in, and Complexity Visualizer shows why the curve bends the way it does — it isn't a straight line getting steeper, it's a fundamentally different shape than O(n).

The fix, and why it isn't a small win

The problem is the repeated linear scan, not the loop itself. A Set turns membership checking from an O(n) scan into an O(1) average-case lookup, which turns the whole function from O(n²) into O(n):

function hasDuplicates(emails) {
  const seen = new Set();
  for (const email of emails) {
    if (seen.has(email)) return true; // O(1) average, not O(n)
    seen.add(email);
  }
  return false;
}

At 1,000,000 signups, the O(n) version does 1,000,000 operations instead of 1,000,000,000,000 — about 10 milliseconds instead of 2.8 hours. That's not an optimization in the usual sense of shaving off a percentage; it's a million-times speedup, because n² ÷ n = n, and n is a million. Every time an O(n²) function becomes O(n) at size n, that's the size of the speedup, by definition — the bigger the input that was hurting, the more dramatic the fix.

Where else this hides

The duplicate-check above is the classic non-nested case, but O(n²) shows up in a few recognizable shapes:

• An array method that scans, called inside a loop — .indexOf(), .includes(), .find(), or a manual scan, run once per element of another collection. This is the version that doesn't look nested and is the easiest to miss in review.
• Genuinely nested loops — all-pairs comparisons: nearest-neighbor checks, collision detection between every pair of objects, naive similarity or distance calculations across a growing dataset. These at least look like what they are.
• O(n²) sorting algorithms left in place past the point they should've been swapped out — Bubble Sort, Selection Sort, or Quick Sort hitting its worst case on already-sorted input. Sorting Algorithm Visualizer shows Quick Sort with a last-element pivot doing exactly n(n-1)/2 comparisons — 435, for 30 already-sorted elements — on data that looks like the easy case and is actually the worst one.

When O(n²) is genuinely fine

None of this means quadratic algorithms are a mistake on sight. Look back at the table above — at a few thousand elements or fewer, O(n²) is comfortably sub-second, and rewriting it buys nothing a user or a system will ever notice. Two real production implementations make exactly this trade deliberately, as covered in Algorithm Complexity Explained: Python's Timsort falls back to an O(n²)-worst-case insertion sort for runs under 64 elements, and C++'s std::sort does the same under 16 — in both cases because the simpler algorithm's lower constant factor wins outright at that size, and the asymptotically better algorithm's overhead isn't worth paying for yet.

The size where this stops being true isn't universal — it depends on what's actually inside the loop, and on how fast n is realistically going to grow. A one-time migration script running against 200 rows a single time doesn't need a rewrite. A hot path on a table that gains 10,000 rows a month absolutely does, eventually — the question worth asking isn't "is this O(n²)" on its own, it's "is this O(n²) on data that's going to grow past the point in that table where it stops being free."

Catching it before it ships

• Test with realistic volumes, not fixture-sized ones. 100 rows and 100,000 rows can pass the exact same test suite while being separated by the gap in the table above.
• Read for the pattern, not just the braces — a scanning array method inside any loop is the same shape as a nested loop, just spelled differently. See Big O Notation Explained with Real Examples for more of these.
• Do the arithmetic before shipping, not after the alert fires. Big O Calculator gives the exact operation count at your real (or realistically projected) data size, and Algorithm Runtime Estimator turns that count into the number that actually matters: how long it takes.

Try it yourself

Algorithm Runtime Estimator reproduces every row of the table above — plug in your own input size and throughput instead of trusting the defaults. Complexity Visualizer plots the O(n²) curve against O(n) and O(n log n) so you can watch how much the gap between them changes as you drag the input size up, and Sorting Algorithm Visualizer shows real O(n²) behavior — comparisons and swaps actually counted, not estimated — on six different sorting algorithms. All three run entirely in your browser.

FAQ

Is a Set always the fix for O(n²)?

It's the fix for the specific pattern in this post — repeated membership checks against the same collection. Other O(n²) shapes need different fixes: sorting first and then doing a single linear pass, a smarter algorithm for the specific problem (e.g. a spatial index instead of all-pairs distance checks), or restructuring to avoid recomputation. The common thread is the same one covered in Algorithm Complexity Explained: trading some space for less time, in whatever shape the specific problem allows.

How do I know if my n is going to grow enough to matter?

Look at where the data actually comes from. A list scoped to one user's own records might have a natural, small ceiling. A table that grows with total signups, total orders, or total events across the whole system usually doesn't — and those are exactly the ones worth checking against the table above before they're large enough to hurt.

Is anything on this page measuring my actual code?

No — the numbers here are worked examples at a fixed, typical throughput. For your own function, Algorithm Runtime Estimator and Big O Calculator take your own input size and complexity class, entirely in your browser — nothing is sent to a server.

Does this come up in interviews?

Constantly, usually as the gap between a candidate's first working answer and the follow-up question "can you do better?" See Time Complexity Interview Guide for exactly this Set-based fix worked through the way you'd actually explain it out loud.