Time & space complexity (Big-O)

Status: 🟩 COMPLETE Last updated: 2026-06-19 Plain-English tagline: A shorthand for “how does this code’s speed and memory usage change as the input grows?” — O(1), O(log n), O(n), O(n²) etc. The vocabulary developers use when comparing approaches without running them.

In plain English

If you have an algorithm and you want to know “is this fast?”, the most useful question is: as the input gets bigger, how much SLOWER does it get?

A few patterns appear over and over:

Constant time — O(1): “Same speed no matter how big the input.” Looking up a value in a hash map by key.
Logarithmic — O(log n): “Slows down a little as input grows, but very slowly.” Binary search in sorted data.
Linear — O(n): “Twice the input, twice the time.” Scanning a list once.
Linearithmic — O(n log n): “A bit worse than linear.” Sorting (the best general-purpose sorts).
Quadratic — O(n²): “Twice the input, FOUR times the time.” Nested loops over the same data. Famous for “fine at 1000 items, dies at 100,000.”
Exponential — O(2ⁿ): “Adding one item DOUBLES the time.” Brute-force “try every possible subset” approaches.

The notation is called Big-O (or “big-oh”). It captures the WORST-CASE growth rate, ignoring constant factors. So “100×n” and “n” are both O(n) — the same big-O class.

This is the language developers use for comparing approaches:

“We changed array.includes() (O(n)) to set.has() (O(1)) and the page got 10× faster.”
“The nested loop is O(n²) — at 10,000 users it’ll time out.”
“Quick sort is O(n log n) on average — fast enough.”

For Bible Quest-scale projects, you’ll rarely need to OPTIMIZE for Big-O — most data is small. But READING the language matters constantly.

For the data structures these algorithms operate on, see Data structures — overview. For specific algorithms, see Algorithms — intro.

Why it matters

Three concrete reasons:

Reading code/comments. “This is O(n²)” tells you something specific. Without the vocab, it’s noise.
Catching slow code BEFORE it’s slow. An O(n²) loop that’s fine for 100 items is catastrophic at 100,000. Recognizing the pattern early avoids the surprise.
Comparing options without benchmarks. “Should I sort first then search, or search linearly each time?” — Big-O gives the answer without running anything.

The trade-off: Big-O ignores CONSTANT FACTORS and SMALL DATA. An algorithm with a “better” Big-O can be slower in practice for small input. Profile real bottlenecks; don’t optimize on Big-O alone.

How to read O(…)

Examples:

O(1) — “constant” — doesn’t depend on input size
O(n) — “linear in n” — n is the input size
O(n²) — “n squared” — n times n
O(log n) — “log n” — usually log base 2; doesn’t matter for the class
O(n log n) — “n log n” — n times log n
O(2ⁿ) — “2 to the n” — exponential
O(n!) — “n factorial” — even worse than exponential

What “n” means depends on context:

For an array operation, n = array length
For a graph algorithm, n = number of nodes (sometimes m = number of edges)
For a string algorithm, n = string length

Sometimes multiple variables: O(n + m) for an algorithm proportional to both array sizes.

The classes ranked by speed

For large input (n = 1 million), here’s how long each takes (rough orders of magnitude):

Complexity	Operations for n=1M	Notes
O(1)	1	Hash lookup, array indexing
O(log n)	~20	Binary search
O(√n)	1,000	Some specialized algorithms
O(n)	1,000,000	One pass through the data
O(n log n)	~20M	Good sorts
O(n²)	1,000,000,000,000	Nested loops — slow at scale
O(n³)	10¹⁸	Triple-nested loops — impractical
O(2ⁿ)	2^1,000,000	Astronomical
O(n!)	(1M)!	Beyond astronomical

At n=1,000:

O(n²) = 1M operations — still fast (milliseconds)
O(n³) = 1B operations — noticeable lag (seconds)

At n=100,000:

O(n²) = 10B operations — likely too slow for interactive use
O(n³) = 10¹⁵ — definitely too slow

Rule of thumb: For an “interactive” UI (under 100ms response), keep total operations under ~10M.

Common operations and their Big-O

A reference table for code you’ll encounter:

Operation	Big-O
`array[i]` (index access)	O(1)
`array.push(x)` (add to end)	O(1)
`array.pop()`	O(1)
`array.shift()` (remove from front)	O(n)
`array.unshift(x)` (add to front)	O(n)
`array.includes(x)` / `indexOf(x)`	O(n)
`array.sort()`	O(n log n)
`array.filter(...)`	O(n)
`array.map(...)`	O(n)
`array.reduce(...)`	O(n)
`Map.get(k)`, `Map.set(k, v)`, `Map.has(k)`	O(1) average
`Set.has(x)`, `Set.add(x)`	O(1) average
`obj[k]` (property access)	O(1) average
`JSON.parse(str)`	O(n) where n = string length
`JSON.stringify(obj)`	O(n) where n = object size
Nested for loop over same array	O(n²)
Binary search in sorted array	O(log n)
Database SELECT with index	O(log n)
Database SELECT without index	O(n)
Database SELECT with JOIN (no index)	O(n × m) potentially

Notice the recurring theme: hash-based lookups are O(1); ordered lookups are O(log n); scanning is O(n).

A concrete example: the same problem, different complexities

Task: “Given two arrays of users, find the ones in both.”

Approach 1 — Nested loops (O(n × m))

function findCommonUsers(usersA, usersB) {
  const common = [];
  for (const a of usersA) {
    for (const b of usersB) {
      if (a.id === b.id) common.push(a);
    }
  }
  return common;
}

For 1,000 users in each: 1,000,000 comparisons. Slow but works.

Approach 2 — Build a set (O(n + m))

function findCommonUsers(usersA, usersB) {
  const idsB = new Set(usersB.map(u => u.id));    // O(m)
  return usersA.filter(a => idsB.has(a.id));       // O(n)
}

For 1,000 users in each: 2,000 operations. 500× faster.

Same result; vastly different performance. Recognizing the pattern (lookup → use a Set) is the skill.

How to ESTIMATE Big-O in code

Quick rules:

A single loop over n items: O(n)
Nested loops: multiply. Two nested loops over n: O(n²). Loop over n inside loop over m: O(n × m).
Halving each iteration: O(log n). Binary search, divide-and-conquer.
Repeated halving + linear work: O(n log n). Most sorts.
Recursion: depends on the branching factor. Each call splits into 2 → could be O(2ⁿ).
Hash table operations: O(1).
Sorting + then doing something with the sorted data: O(n log n) + whatever.

Walking through code:

// O(n) for the loop
// Each iteration: O(1) Set.has + O(1) Set.add
// Total: O(n)
const seen = new Set();
for (const item of items) {
  if (seen.has(item)) continue;
  seen.add(item);
}
 
// O(n) for outer loop
// Each iteration: O(m) Array.includes
// Total: O(n × m)
for (const a of arrayA) {
  if (arrayB.includes(a)) { ... }
}
 
// O(n log n) for sort
// O(n) for the loop
// Total: O(n log n)
const sorted = [...items].sort();
for (const x of sorted) { ... }

After a while, you “see” the complexity by reading the code.

Space complexity

The same idea but for MEMORY USED.

O(1) space: uses a fixed amount of memory regardless of input size
O(n) space: memory grows linearly with input
O(n²) space: memory grows with the square of input — usually a bad sign

Examples:

// O(1) extra space — uses just a few variables
function sum(arr) {
  let total = 0;
  for (const x of arr) total += x;
  return total;
}
 
// O(n) extra space — builds a new array of the same size
function doubled(arr) {
  return arr.map(x => x * 2);
}
 
// O(n) extra space — builds a set as big as the array
function unique(arr) {
  return [...new Set(arr)];
}
 
// O(n²) space — explicitly bad: stores all pairs
function allPairs(arr) {
  const pairs = [];
  for (const a of arr) for (const b of arr) pairs.push([a, b]);
  return pairs;
}

Most webapp work cares less about space than time. Memory is cheap; CPU time is the bottleneck. But for large datasets (or memory-constrained environments like browser tabs), space matters too.

The big-O / actual-time relationship

A common misunderstanding: “O(n) means fast.” Big-O ignores constant factors and small input. So:

An “O(n) algorithm” that does 1,000,000 operations per element can be slower than an “O(n²) algorithm” that does 2 operations per pair (for small n).
A clever O(n log n) algorithm with high overhead can be slower than a brute-force O(n²) for arrays under, say, 100 items.

This is why JavaScript’s Tim sort switches to insertion sort (O(n²) in theory) for small subarrays — the constant factors are better for small data.

Big-O tells you asymptotic growth. Real performance depends on constant factors + cache behavior + actual input distribution. Profile when it matters; reason in Big-O when it doesn’t.

A practical heuristic for “is this fast enough?”

For typical webapp work:

Operations per request	User experience
< 100,000	Instant; no need to optimize
100,000 – 1,000,000	Fast; still feels instant
1,000,000 – 10,000,000	Noticeable but acceptable
10,000,000 – 100,000,000	Slow; users feel it
> 100,000,000	Pretty much broken

So:

O(n²) at n=1,000 → 1M ops → fast
O(n²) at n=10,000 → 100M ops → SLOW
O(n log n) at n=1,000,000 → 20M ops → fast
O(n) at n=10,000,000 → 10M ops → fast

The sweet spot for “things that scale” is O(n) or O(n log n). Beyond that, the input size becomes the limit.

Common gotchas

Big-O hides constants. O(n) might do 1 operation per item or 1000. The class is the same; the runtime isn’t.
Big-O is about WORST case unless specified. Quick sort is O(n²) worst case (pathological input) but O(n log n) on average. Hash table lookups are O(1) average but O(n) worst case.
includes and indexOf are O(n). Easy to overlook. If you’re searching the same array many times, convert to a Set ONCE.
Array.prototype.shift() is O(n). Every item shifts. For high-volume “FIFO queue” code, use a real queue library or batch.
String concatenation in a loop is O(n²) in some languages — JavaScript handles this well (modern engines optimize), but for huge string-building, use array.join('') instead.
Sort is O(n log n), not O(n). Easy to forget when planning.
Don’t optimize prematurely. A clear O(n²) for 100 items is better than a clever O(n) that nobody understands.
Profile, don’t guess. Big-O is asymptotic; real performance can surprise you. Use the browser DevTools Performance tab or Node’s --prof.
Memoization adds memory. useMemo caches a value forever (until dependencies change). For 1M items, that’s a lot of cached data.
for vs forEach matters for hot paths. Modern V8 optimizes both, but in tight loops for is sometimes 2-3× faster.
Generators are lazy; Array.from(generator) is eager. A generator iterating over 1B items is fine if you stop early; collecting into an array uses 1B units of memory.
Regular expressions can be O(2ⁿ). “Catastrophic backtracking” — certain regex patterns explode on long input. Real DoS vector. Use linear-time regex engines (RE2) for user input.
Stack overflow from deep recursion. ~10,000 deep in JavaScript. For trees of depth 10,000, convert to iteration. Tail-call optimization isn’t reliably implemented in V8.
The N+1 query problem in databases. Fetching 100 users + then 1 query each for their posts = 101 queries. Use JOINs or batch loading. Same Big-O concept, scaled to network round-trips.
Cache locality matters at low level. Operations on contiguous memory (arrays) are faster than the same Big-O ops on scattered memory (linked lists, large objects). Mostly invisible in JavaScript; matters at C/C++ level.
AI tools sometimes write O(n²) when O(n) exists. Especially for “find duplicates,” “intersect arrays,” “find common items.” Recognize the pattern and rewrite with Set/Map.
Big-O of a single API call is misleading. A single fetch may take 200ms regardless of data size. Algorithmic Big-O doesn’t capture network latency. Often “make fewer calls” beats “faster algorithm per call.”
Object.keys(obj).length is O(n). If you need size often, use a Map (.size is O(1)) or track separately.
Spreading is O(n). [...arr, item] is O(n) for the spread. Repeated spreads in a loop = O(n²). Use mutation (arr.push(item)) or batch when possible.
Don’t conflate “looks complex” with “high complexity.” A 50-line function with a single loop is still O(n). A 3-line function with nested loops is O(n²). Look at LOOPS, not LINE COUNT.
“Online” algorithms process data as it arrives — O(1) per item, even if you process N items total. Streaming, real-time, low-latency apps prefer these.
Big-O class is invariant under constant multipliers and lower-order terms. O(2n + 5) = O(n). O(n² + n) = O(n²). The dominant term wins.
For tiny data, BIG-O DOESN’T MATTER. Sort 5 items with bubble sort or merge sort — both finish in microseconds. Pick the simpler code.

What you DON’T need to memorize

Exact running time formulas (just the class)
Mathematical proofs of complexity (rare in webapp work)
Master Theorem (for analyzing divide-and-conquer recurrences — niche)
Amortized analysis subtleties (when “average over many ops” gives a different class)

What’s enough: recognize O(1) / O(log n) / O(n) / O(n log n) / O(n²) / O(2ⁿ) when you see them in code or conversation.

Sources

Big-O Cheat Sheet — visual reference for common operations
MDN — Algorithms
Wikipedia — Big O notation
Introduction to Algorithms (CLRS) — Chapter 3 — the formal definition
Computational Complexity (free online textbook)

Tech & AI, Explained

Explorer

time-and-space-complexity