Big-O where it actually bites

What it is

Big-O describes how work grows as input grows. In college it was a proof exercise. In production it is a code-review reflex: you are looking for the moment where doubling the data quadruples the time.

Why it bites

Nobody ships an O(n²) sorting algorithm. They ship this:

for (const order of orders) {
  const user = await db.users.findById(order.userId)
  order.userName = user.name
}

That is O(n) database round trips, and each round trip costs 1–5 ms of network time. With 20 orders in your test data it takes 60 ms and looks fine. With 5,000 orders in production it takes 15 seconds, holds a connection from the pool the whole time, and the pool exhausts under concurrent requests. The endpoint does not get slow — the whole service does.

The fix is one query:

const users = await db.users.findByIds(orders.map(o => o.userId))
const byId = new Map(users.map(u => [u.id, u]))

Two round trips instead of 5,000. This is the same N+1 pattern you will meet again in query plans and N+1.

The same work, two shapes: a round trip per row versus one batched query.

The mental model

Ask two questions of any loop:

1. What is inside it that leaves the process? A query, an HTTP call, a file read, a JSON.parse of something large. Work inside a loop that crosses a process boundary is the expensive kind.
2. What is the realistic worst-case n? Not today's n — the n after a year of growth or one enterprise customer who imports 200,000 rows.

Constants matter more than the exponent at small n, and almost all real n is small. An O(n²) loop over 50 in-memory items is genuinely fine. An O(n) loop making network calls over 50 items is not. Complexity class alone does not tell you which is which; what the loop body does is the other half.

Gotchas

• Nested array.includes() or array.find() inside a loop is a hidden O(n²). Build a Set or Map first.
• String concatenation in a loop is O(n²) in some runtimes. Push to an array and join.
• Sorting inside a loop is the classic accidental O(n² log n).
• An index makes a lookup O(log n) instead of O(n) — but only if the query can use it.
• Pagination bounds n for you. An endpoint with no limit is an endpoint with an unbounded worst case.

Prove you know it

Open the slowest endpoint you have written. Count the round trips it makes for a single request, then work out what that number is when the underlying collection has 10,000 rows. If the answer is "10,000", you have found your first fix.