Complexity — sizing speed and memory with big-O

When you say "this code is slow", what are you basing it on? Measurements depend on the environment, and code that's fast on your dev machine can fall apart at production data sizes.

Complexity is a way to express speed as how the amount of work grows as the input grows. It doesn't depend on the machine, so you can estimate it just by reading the code.

What you'll learn in this chapter

What big-O expresses and what it throws away
How different the common orders actually feel at real data sizes
The distinction between time and space complexity
The procedure for counting orders from code
When to use worst / average / best cases

Prerequisites

If you have written loops and recursion in any language, you can read this. No mathematical background needed.

What it looks at, and what it ignores

Big-O expresses how growth changes as input size n increases. It's not the absolute execution time.

To do that, it throws away two things.

Constant factors — both 2n and 100n are written O(n)
Lower-order terms — n² + 1000n + 5 is written O(n²)

It looks crude, but the purpose is to see what dominates when n is large enough. For n² + 1000n with n at a million, n² is a trillion and 1000n is a billion — the second is under 0.1%. The larger the scale, the more the fastest-growing term alone decides the result.

The flip side: at small n, the ranking under big-O can invert. It's not unusual for a simple O(n²) algorithm to beat a complex O(n log n) one, because of constant factors. That's why real language sort implementations switch to insertion sort for small arrays.

Common orders

Notation	Name	Typical example
`O(1)`	Constant time	Array indexing, hash-map get (average)
`O(log n)`	Logarithmic time	Binary search, balanced BST lookup
`O(n)`	Linear time	Full array scan, linear search
`O(n log n)`	Linearithmic time	Common sorts (merge sort; quicksort on average)
`O(n²)`	Quadratic time	Nested loops, naive sorts
`O(2^n)`	Exponential time	Enumerating all subsets

The numbers make the difference feel real. At 1 nanosecond per step, this is what happens as n grows.

n	`O(log n)`	`O(n)`	`O(n log n)`	`O(n²)`
1,000	~10	1,000	~10,000	1,000,000
1,000,000	~20	1,000,000	~20,000,000	1 trillion
1 billion	~30	1 billion	~30 billion	10^18

O(log n) barely grows. Multiplying data by 1,000 adds about 10 to the work. That's what powers binary search, and it's the same reason database indexes speed up lookup. Meanwhile O(n²) at a million items becomes a trillion steps, which is 16 minutes at 1 nanosecond per step. Not practical.

Whether you can answer "what happens if data grows 10×" is a good gauge for whether you're using big-O. O(n) gives 10×, O(n²) gives 100×, O(log n) barely changes.

Time complexity and space complexity

There are two kinds of complexity.

	What it measures
Time complexity	Number of processing steps
Space complexity	Additional memory the work needs

Space complexity counts what's added on top of the input itself. Accepting a length-n array and using a handful of variables is O(1). The input array is not counted.

// Space complexity O(1) — just two extra variables
function sum(numbers: number[]): number {
  let total = 0;
  for (const n of numbers) {
    total += n;
  }
  return total;
}

// Space complexity O(n) — creates a new array of the same length
function doubled(numbers: number[]): number[] {
  return numbers.map((n) => n * 2);
}

The recursion call stack is counted as space. A function that recurses to depth n has space complexity O(n) even if each level uses only one variable. This is easy to miss — the same algorithm can have different space complexity depending on whether it's written iteratively or recursively.

Counting from code

Nested loops multiply

// O(n)
for (let i = 0; i < n; i++) {
  doSomething();
}

// O(n²) — outer n times × inner n times
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    doSomething();
  }
}

// O(n²) — inner averages n/2 but constants drop
for (let i = 0; i < n; i++) {
  for (let j = i; j < n; j++) {
    doSomething();
  }
}

The third one has inner counts n, n-1, ..., 1 summing to n(n+1)/2. Dropping constant factors and lower-order terms leaves O(n²).

Logs appear when "you cut it to some fraction each time"

// O(log n) — remaining halves each round
let remaining = n;
while (remaining > 1) {
  remaining = Math.floor(remaining / 2);
}

Halving down to 1 takes log₂ n rounds. Find a structure that discards a fixed fraction each round, and think "log" — that's the source of binary search's speed.

Watch for hidden loops

// Looks O(n), actually O(n²)
for (const item of items) {
  if (others.includes(item)) {   // includes internally scans in O(m)
    result.push(item);
  }
}

includes and indexOf scan the array in O(m). Calling them inside a loop multiplies. Converting others into a Set makes the check average O(1), dropping the whole thing to O(n + m).

Don't count library functions as "one step". Without knowing what they do inside, you'll misread the order.

Besides hashing, there are other patterns for reducing a nested loop to a single pass. Which one applies is organized in Array scanning patterns.

Worst, average, and best

The same algorithm can take different amounts of work depending on the input.

	Meaning	Where to use
Worst-case	Value on the input requiring the most work	Where a guarantee is needed. Big-O usually refers to this
Average-case	Expected value on unskewed input	Practical rule of thumb
Best-case	Value on the input requiring the least work	Rarely used

Hash maps are the classic example. Get is average O(1), but if all keys collide to the same hash they end up traversing a single chain, becoming worst O(n). It's the worst case that makes hash-flooding attacks possible.

Quicksort is average O(n log n), worst O(n²). Choosing a good pivot is what dodges the worst case.

Common misconceptions

"O(n²) is always slower than O(n log n)." — At small n they can flip. Big-O drops constant factors, so it's not an absolute-speed comparison.

"Same complexity means same execution speed." — Wrong. Two O(n) functions can differ by 100× if constants differ by 100×. Big-O answers only "how it grows".

"Space complexity includes the input size." — Usually not. It counts additional memory beyond the input.

"Space complexity doesn't change with recursion." — It does. The call stack stacks up to the recursion depth.

"Hash maps are always O(1)." — Average is O(1), worst is O(n).

Exercises

Q1. State the time and space complexity of this function.

function hasDuplicate(numbers: number[]): boolean {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) return true;
    }
  }
  return false;
}

Answer and explanation

Answer: Time O(n²), space O(1)

The double loop has inner counts n-1, n-2, ..., 1, summing to n(n-1)/2. Dropping constants and lower-order terms gives O(n²).

The only extra allocations are two counter variables, so space is O(1). The input array isn't counted.

This can be improved to time O(n) and space O(n) using a Set — the classic spend memory to buy time trade-off.

function hasDuplicateFast(numbers: number[]): boolean {
  const seen = new Set<number>();
  for (const n of numbers) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

Q2. What is the space complexity of this recursive function?

function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

Answer and explanation

Answer: O(n)

Each level uses just one argument, but factorial(n) calls factorial(n-1), which calls factorial(n-2), and so on to depth n. This call stack is the space complexity.

Written as a loop, the same computation has space complexity O(1).

function factorialLoop(n: number): number {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

Time complexity is O(n) in both cases. Only space differs.

Q3. A process takes 1 second on 1,000 items. How long will it take on 1,000,000 items? Answer for both O(n) and O(n²).

Answer and explanation

Answer: O(n) about 1,000 seconds (~17 min); O(n²) about 1,000,000 seconds (~11.6 days)

Data grew 1,000×.

O(n) — work grows 1,000×. 1 s × 1,000 = 1,000 s
O(n²) — work grows 1,000² = 1,000,000×. 1 s × 1,000,000 = 1,000,000 s

The intuition "1 s on 1,000 items means a few seconds on a million" is completely wrong under O(n²). This is the structure by which algorithms that don't show problems on small dev data blow up at production sizes.

For O(log n), the same jump takes only about 2 seconds.

Summary

Big-O expresses how work grows with the input, dropping constants and lower-order terms
Because constants are dropped, rankings can flip at small n
Time complexity is step count; space complexity is additional memory beyond the input
The recursion call stack counts toward space complexity
Nested loops multiply; a structure that discards a fixed fraction each round is logarithmic
Don't count library functions as one step. includes and similar scan internally
Hash maps are average O(1), worst O(n)

Related references

Database Design Guide — Introduction to index design — How a B-Tree makes lookup logarithmic

What you'll learn in this chapter​

What it looks at, and what it ignores​

Common orders​

Time complexity and space complexity​

Counting from code​

Nested loops multiply​

Logs appear when "you cut it to some fraction each time"​

Watch for hidden loops​

Worst, average, and best​

Common misconceptions​

Exercises​

Summary​

What to read next​

What you'll learn in this chapter

What it looks at, and what it ignores

Common orders

Time complexity and space complexity

Counting from code

Nested loops multiply

Logs appear when "you cut it to some fraction each time"

Watch for hidden loops

Worst, average, and best

Common misconceptions

Exercises

Summary

What to read next