Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Big O Notation Explained

What Big O notation measures, the common complexity classes from O(1) to O(2^n), and how to work out the time and space complexity of your own code.

· Updated · 10 min read

Big O notation describes how the cost of an algorithm grows as its input grows. It does not tell you how many milliseconds something takes. It tells you what happens to the running time when the input becomes ten or a thousand times larger.

What Big O measures

We count the number of basic steps an algorithm performs as a function of the input size, usually called n. Then we keep only the part that matters when n is large.

function sum(numbers) {
  let total = 0;
  for (const value of numbers) {
    total += value;
  }
  return total;
}

If the array has n items, the loop body runs n times. Double the array and the work doubles. That is O(n), read as "order n" or "linear time".

The common complexity classes

From slowest-growing to fastest-growing:

Notation Name Typical example Steps when n = 1,000
O(1) Constant Reading an array item by index 1
O(log n) Logarithmic Binary search about 10
O(n) Linear One loop over the input 1,000
O(n log n) Linearithmic Efficient sorting, such as merge sort about 10,000
O(n²) Quadratic A loop inside a loop over the same input 1,000,000
O(2ⁿ) Exponential Trying every subset of the input more than 10³⁰⁰

The last column is why this matters. At a thousand items, a quadratic algorithm does a thousand times more work than a linear one, and an exponential one will never finish.

How the classes pull apart

The same table for four input sizes shows how quickly the gaps open up:

n = 10 n = 100 n = 1,000 n = 1,000,000
O(1) 1 1 1 1
O(log n) 3 7 10 20
O(n) 10 100 1,000 1,000,000
O(n log n) 33 664 10,000 20 million
O(n²) 100 10,000 1 million 1 million million
O(2ⁿ) 1,024 more than 10³⁰ more than 10³⁰⁰ beyond writing down

At ten items nothing matters: every row is tiny. At a million, the difference between O(n log n) and O(n²) is the difference between a blink and several hours.

What fits in a second

As a rough guide, a modern computer gets through somewhere around a hundred million simple steps a second. That turns the table into a practical question: how big can n be before the wait becomes noticeable?

Complexity Largest n that stays around a second
O(n) About 100 million
O(n log n) A few million
O(n²) About 10,000
O(2ⁿ) About 25

These are orders of magnitude, not promises. But they are useful in reverse: if a problem says the input can hold a million items, an O(n²) solution is not going to be accepted.

How to work out the complexity of code

A single loop over the input is O(n).

function contains(items, target) {
  for (const item of items) {
    if (item === target) return true;
  }
  return false;
}

A loop inside a loop over the same input is O(n²). For each of the n items, the inner loop runs up to n times.

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

Halving the remaining work each step is O(log n). If every step discards half of what is left, a million items take about 20 steps. Binary search works this way.

Steps that run one after another are added; steps that are nested are multiplied. Two separate loops over the input are O(n + n), which simplifies to O(n). A loop inside a loop is O(n × n).

Four worked examples

1. A nested loop that is not O(n²). The inner loop here always runs 26 times, whatever the length of the text. That is a constant, so the function is O(26 × n), which is O(n).

function letterCounts(text) {
  const counts = new Array(26).fill(0);
  for (const ch of text.toLowerCase()) {
    for (let i = 0; i < 26; i++) {
      if (ch === String.fromCharCode(97 + i)) counts[i]++;
    }
  }
  return counts;
}

Count loops by how many times they run in terms of the input, not by how deeply they are nested.

2. A loop that halves. The counter is cut in half each time round, so the loop runs about log₂ n times.

function halvingSteps(n) {
  let steps = 0;
  for (let i = n; i > 1; i = Math.floor(i / 2)) {
    steps++;
  }
  return steps;
}
 
console.log(halvingSteps(1000)); // 9
console.log(halvingSteps(1000000)); // 19

A thousand times more input costs ten more steps. Whenever the remaining work is divided by a fixed amount each step, the answer is O(log n).

3. An inner loop that starts part-way. The inner loop gets shorter each time: n − 1 steps, then n − 2, down to 0.

function countPairs(items) {
  let pairs = 0;
  for (let i = 0; i < items.length; i++) {
    for (let j = i + 1; j < items.length; j++) {
      pairs++;
    }
  }
  return pairs;
}
 
console.log(countPairs([1, 2, 3, 4, 5])); // 10

The total is n × (n − 1) ÷ 2. That is half of n², minus a smaller term. Dropping the constant and the smaller term leaves O(n²). Starting the inner loop at i + 1 halves the work but does not change the class.

4. Sort, then loop. Sorting costs O(n log n) and the loop afterwards costs O(n). Steps that follow each other are added: O(n log n + n). The larger term wins, so the whole thing is O(n log n). The sort is the bottleneck, and speeding up the loop would change nothing.

Recursion

For a function that calls itself, multiply the number of calls by the work done in each call.

function slowFibonacci(n) {
  if (n < 2) return n;
  return slowFibonacci(n - 1) + slowFibonacci(n - 2);
}
 
console.log(slowFibonacci(10)); // 55

Each call makes two more, each of which makes two more, so the number of calls roughly doubles every time n goes up by one. That is exponential: O(2ⁿ). slowFibonacci(10) is instant, slowFibonacci(50) takes minutes, and remembering the answers already worked out brings it down to O(n).

Recursion also uses memory. Every call that has started and not yet finished is waiting on the call stack, so a function that recurses n levels deep uses O(n) space even if it creates no arrays.

The two simplification rules

Drop constants. O(2n) and O(n/2) are both written O(n). Big O describes the shape of the growth, and a constant factor does not change the shape.

Keep only the fastest-growing term. O(n² + n) is written O(n²). When n is a million, the n² part is a million times larger than the n part, so the smaller term stops mattering.

One caution: use a different letter for each independent input. Looping over one list of length a and, inside it, another of length b is O(a × b), not O(n²).

Space complexity

The same notation describes extra memory. Count the memory the algorithm allocates in addition to its input.

  • A few variables, whatever the input size: O(1) space.
  • A new array or hash table that can grow to the size of the input: O(n) space.

Many optimisations trade one for the other. Finding a duplicate with a nested loop takes O(n²) time and O(1) space. Remembering the values you have seen in a hash set takes O(n) time and O(n) space.

Amortised cost

Some operations are cheap almost every time and expensive once in a while. Adding to the end of an array is the standard example: usually it writes one item, but occasionally the array is full and everything has to be copied to a bigger block.

Averaged over many additions, the cost per addition is still constant, so it is described as amortised O(1). The word is a warning as much as a reassurance: the average is constant, but an individual call can be slow.

Best, average and worst case

contains above returns immediately if the target is the first item and scans everything if it is missing. Unless stated otherwise, Big O refers to the worst case, because that is the guarantee you can rely on.

The three cases can be very different. Looking up a key in a hash table is O(1) on average and O(n) in the worst case, and both figures are worth quoting.

More classes you will meet

Notation Where it comes from
O(n + m) Two separate inputs, each looped over once
O(n × m) A loop over one input inside a loop over another, such as every cell of a grid
O(n × k) For each of n items, k steps, such as a window of size k recalculated each time
O(√n) Checking possible divisors of a number only up to its square root
O(n!) Trying every ordering of the input. Unusable beyond about 10 items

Saying it out loud in an interview

When asked for the complexity of a solution, a complete answer has four parts:

  1. What n is. "Where n is the length of the array."
  2. The time, with the reason. "O(n), because it is a single pass and each lookup is constant."
  3. The space, with the reason. "O(n) extra, for the set of values seen."
  4. Any assumption. "That is the average case for the hash set."

Starting with the brute-force solution and its cost, then naming the part that makes it slow, is usually the quickest route to the better solution. Contains Duplicate walks through three solutions to one problem at O(n²), O(n log n) and O(n).

Common mistakes

  • Counting hidden loops as one step. array.includes(x), array.indexOf(x) and array.shift() each loop over the array. Calling one of them inside a loop gives O(n²).
  • Assuming fewer lines means faster. A one-line chain of filter and map is still O(n) per call.
  • Ignoring the size of the input. For ten items, the difference between O(n) and O(n²) is irrelevant. Big O matters when n is large.
  • Calling a nested loop O(n²) without looking. If the inner loop runs a fixed number of times, or the two loops together visit each item once, it is O(n).
  • Forgetting the call stack. Deep recursion costs memory even when no data structure is created.
  • Using n for two different things. Name each input separately, then simplify.

Summary

  • Big O describes how cost grows with input size, not how long something takes.
  • Drop constants and keep the fastest-growing term.
  • One loop is O(n). A loop inside a loop over the same input is O(n²). Halving each step is O(log n).
  • Steps in sequence are added. Nested steps are multiplied.
  • The same notation measures extra memory, and time is often traded for it.
  • Unless told otherwise, quote the worst case.

Next: how arrays work and what each array operation costs.