Here's a story that plays out on almost every team sooner or later. The code passed review. The tests were green. It handled the sample file of 200 rows instantly. Then someone uploaded a real import file, and the request timed out.

Nothing was "wrong" with the code. It was just O(n²), and 200 rows was small enough to hide it.

Big O has a reputation as interview trivia, something you memorise for a whiteboard and forget. I think that's backwards. It's one of the most practical ideas in programming, and you don't need any maths beyond "what happens when the data doubles?"

The one question Big O answers

Big O describes how the work grows as the input grows. Not how fast code is in seconds, but how it scales.

So the useful question is: if my data doubles, what happens to the work?

That last row is where most real trouble lives. At 200 items, n² is 40,000 steps: nothing. At 20,000 items it's 400 million. Same code, a hundred times more data, ten thousand times more work.

The hidden loop

Here's the thing: the nested loops that hurt are rarely two obvious foreach blocks. One of them is usually hiding inside a function call.

// Find invoices whose tenant is no longer active
$orphaned = [];
foreach ($invoices as $invoice) {
    if (! in_array($invoice->tenant_id, $activeTenantIds)) {
        $orphaned[] = $invoice;
    }
}

One loop, right? But in_array() walks through $activeTenantIds from the start every time. That's a loop inside a loop: O(n × m). Fine with a few hundred of each, painful with tens of thousands.

The fix is to turn the list into a lookup table once. PHP arrays are hash tables, so isset() on a key is O(1) on average:

$active = array_flip($activeTenantIds); // values become keys, once: O(m)

$orphaned = [];
foreach ($invoices as $invoice) {
    if (! isset($active[$invoice->tenant_id])) {
        $orphaned[] = $invoice;
    }
}

Now the whole thing is O(n + m). Same result, and it scales in a straight line.

The same pattern appears everywhere under different names:

• Laravel collections: ->contains(), ->firstWhere() or ->where() inside a loop. Use ->keyBy('id') once and look up by key.
• JavaScript: array.includes() or array.find() inside .filter() or .map(). Build a Set or Map first.
• Queues of work: array_shift() in a loop. It re-indexes the whole array on every call, so draining an array that way is quietly O(n²).

Big O in the database

Databases are where Big O stops being theoretical, because tables grow forever and nobody resets them.

• No index: WHERE email = ? is a full table scan. O(n). Fine at a thousand rows, slow at ten million.
• With an index: the database walks a B-tree, which is O(log n). Going from a thousand rows to a million adds only a few extra steps. That's why indexes feel like magic.
• A join on an unindexed column can become a nested loop across two tables: hello again, O(n × m).
• N+1 queries are O(n) in round trips. Each query is fast, but a hundred rows means a hundred and one trips to the database. Eager loading with with() makes it a constant two.

When I look at a slow page, this is the first lens I use: which part grows with the data, and how fast?

When Big O doesn't matter

Big O describes growth, so it ignores constants. That has two practical consequences:

• For small, bounded data, it barely matters. A nested loop over the twelve months of a year is fine forever. Don't make code harder to read to optimise something that can't grow.
• Constants can beat complexity. One database query that's O(n) in theory will usually beat a thousand O(1) cache calls over the network. Network round trips, disk access and memory dominate real performance at everyday sizes.

The real question isn't "is this O(n²)?" It's "is n bounded?" If n is the number of months, statuses or settings, relax. If n is users, invoices, rows, uploads or log lines, it will grow, and it will find your quadratic loop eventually.

The cheat sheet

• Ask "what happens when the data doubles?"
• Look for hidden loops inside function calls.
• Turn repeated searches into key lookups: array_flip, keyBy, Set, Map.
• Indexes turn O(n) scans into O(log n) lookups.
• Test with realistic data volumes, not just the seed data.
• Don't optimise what can't grow.

What's the sneakiest O(n²) you've found hiding in a codebase? Mine are almost always an innocent-looking in_array inside a loop.