Time and Space Complexity
Date: 2026-08-17
How the cost of an operation grows as the input grows. Big O is a tool for deciding between two approaches before writing either — not an interview ritual, and not a claim about speed.
Time complexity describes how the number of operations scales with input size. Space complexity does the same for memory. Big O notation expresses the growth rate, discarding constants and lower-order terms.
It is about growth, not speed. An O(n²) algorithm can beat an O(n log n) one at small n. What Big O tells you is what happens when n gets large — which is exactly when you can’t fix it easily.
The growth rates, with real numbers
n=10 n=1,000 n=1,000,000
O(1) 1 1 1
O(log n) 3 10 20
O(n) 10 1,000 1,000,000
O(n log n) 33 10,000 20,000,000
O(n²) 100 1,000,000 1,000,000,000,000
O(2ⁿ) 1,024 ... heat death
Read the bottom right. At a million items, O(n²) is a trillion operations — hours or days. O(n log n) is twenty million — a fraction of a second. The gap between those two rows is the difference between a feature and an outage.
What the notation drops
actual cost: 3n² + 500n + 9000
Big O: O(n²)
Constants and smaller terms are discarded because they stop mattering as n grows. Which is also the notation’s blind spot: at n = 10, that +9000 dominates completely, and the O(n²) term is irrelevant.
In plain terms: Big O answers “what happens when this gets big”, not “which is faster right now”. For small, fixed inputs, measure instead of reasoning.
Reading code for complexity
one loop over n O(n)
nested loop over n O(n²)
loop over n, inner over m O(n × m)
halving each step O(log n)
sort, then one pass O(n log n)
Nested iteration is the thing to look for, and it hides well — a .includes(), .find() or .indexOf() inside a .map() is a nested loop wearing method syntax:
// looks like one loop. is two.
orders.map(o =>
customers.find(c => c.id === o.customerId)
)Space matters too, and gets ignored
O(1) space a few variables, whatever n is
O(n) space a copy of the input
O(n²) space a matrix — rarely acceptable
The usual trade is space for time: build an index (O(n) memory) to turn repeated O(n) searches into O(1) lookups. That’s the right trade almost every time in application code, and it’s what a cache is — Data Structures, Caching Strategies.
Cases you should always check
An average case hides the failure:
best average worst
hash lookup O(1) O(1) O(n) ← collisions
quicksort O(n log n) O(n log n) O(n²) ← bad pivot
regex match O(n) O(n) O(2ⁿ) ← backtracking
The worst case is where outages live, and an attacker who controls the input can often force it — which is the mechanism behind hash-flooding and catastrophic regex backtracking.
Where it actually applies in front-end work
Rarely in the way interviews imply, and constantly in the way they don’t:
- Rendering a list — an O(n²) key lookup inside a render loop is the classic freeze
- Filtering and searching client-side on a large catalogue
- Database queries — the same reasoning, several orders of magnitude more data. An unindexed query is a full scan — Query Planning, N+1 Queries
- Anything called per item in a loop over a network. n round trips is a latency problem, not a CPU one — Latency and Bandwidth
The honest summary: you will almost never calculate a complexity. You will regularly need to notice that something is quadratic before it reaches production.