Lesson 01 of 2416 min read

How Fast Is Fast: Big-O Without the Maths

Every interview answer you give will be judged on this. The good news is that it is counting, not calculus: you look at the loops and you count how the work grows.

By the end: Read any function and say its time and space complexity out loud.

Suppose I give you two functions that both find the largest number in a list. One takes 3 milliseconds, the other takes 5. Which is better?

You cannot answer that. Not because you lack information about the code, but because the question is wrong. Milliseconds depend on the machine, the browser, what else is running, and how warm the JIT is. Change the laptop and the answer flips.

The useful question is: when the input gets bigger, how much more work happens? That question has an answer that does not depend on hardware, and Big-O notation is how we write it down.

Counting, not timing

Here is the whole technique. Look at the loops, and count how many times the innermost line runs.

One loop over n items: the work grows with n

1
2
3
4
5
6
7
8
9
10
11
12
13function largest(list) {
  let steps = 0;
  let best = -Infinity;
  for (const x of list) {
    steps++;                       // this is the line we count
    if (x > best) best = x;
  }
  return { best, steps };
}

console.log(largest([5, 2, 9]));
console.log(largest([5, 2, 9, 1, 7, 3, 8, 4, 6, 0]));
console.log(largest(Array.from({ length: 100 }, (_, i) => i)));

Output

Three items, three steps. Ten items, ten steps. A hundred items, a hundred steps. The steps track the input exactly, so this is O(n).

Now watch what happens when one loop sits inside another.

A loop inside a loop: the work grows with n squared

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function hasDuplicateSlow(list) {
  let steps = 0;
  for (let i = 0; i < list.length; i++) {
    for (let j = i + 1; j < list.length; j++) {
      steps++;
      if (list[i] === list[j]) return { found: true, steps };
    }
  }
  return { found: false, steps };
}

for (const n of [5, 10, 20, 40]) {
  const list = Array.from({ length: n }, (_, i) => i);   // no duplicates: worst case
  console.log('n =', String(n).padStart(2), '→ steps:', hasDuplicateSlow(list).steps);
}

Output

Read those numbers: 10, 45, 190, 780. Every time n doubles, the steps go up about four times. That is the signature of O(n²). At n = 40 it is 780 steps; at n = 40,000 it would be about 800 million.

The ladder

There are only a handful of growth rates you will meet. Learn them in order, best to worst.

O(1) constant. The work does not depend on the input at all. Reading arr[5], pushing onto an array, looking up a key in a Map.
O(log n) logarithmic. Each step throws away half the remaining work. Binary search. Doubling the input adds one step.
O(n) linear. One pass over the input. Summing a list, finding a maximum.
O(n log n). A linear amount of work, log n times. Every good general-purpose sort.
O(n²) quadratic. Every pair. Nested loops over the same input.
O(2ⁿ) exponential. Every subset. Naive recursion that branches twice.
O(n!) factorial. Every ordering. Generating all permutations.

What those growth rates mean at real sizes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19const rates = {
  'O(1)':        () => 1,
  'O(log n)':    (n) => Math.ceil(Math.log2(n)),
  'O(n)':        (n) => n,
  'O(n log n)':  (n) => n * Math.ceil(Math.log2(n)),
  'O(n^2)':      (n) => n * n,
  'O(2^n)':      (n) => (n <= 40 ? 2 ** n : Infinity),
};

const sizes = [10, 100, 1000, 1000000];
console.log('rate'.padEnd(11), sizes.map(s => String(s).padStart(14)).join(''));

for (const [name, f] of Object.entries(rates)) {
  const row = sizes.map(n => {
    const v = f(n);
    return (v === Infinity ? 'too big' : v.toLocaleString('en-US')).padStart(14);
  });
  console.log(name.padEnd(11), row.join(''));
}

Output

Look at the O(n²) row at a million: a trillion operations. A modern machine does very roughly a hundred million simple operations per second in JavaScript, so that is hours. The O(n) row is a million operations, which is a few milliseconds. That gap is the entire reason this topic exists.

Two simplifications that always apply

Big-O throws away detail on purpose, because we only care about the shape of the growth.

Drop the constants. A loop that does three things per item is still O(n), not O(3n). Three passes over the array is O(n) too.

Keep only the biggest term. O(n² + n) is just O(n²), because once n is large the n² part dwarfs everything else.

Three passes is still linear

1
2
3
4
5
6
7
8
9
10
11
12
13function threePasses(list) {
  let steps = 0;
  let sum = 0, max = -Infinity, count = 0;
  for (const x of list) { steps++; sum += x; }
  for (const x of list) { steps++; if (x > max) max = x; }
  for (const x of list) { steps++; if (x > 0) count++; }
  return { steps, ratio: steps / list.length };
}

for (const n of [10, 100, 1000]) {
  const r = threePasses(Array.from({ length: n }, (_, i) => i - 5));
  console.log('n =', String(n).padStart(4), 'steps:', String(r.steps).padStart(5), 'steps per item:', r.ratio);
}

Output

Steps per item stays at exactly 3 no matter the size. The work is a fixed multiple of n, so it is linear. Compare that with the nested-loop version, where steps per item kept climbing.

The hidden loops

This is where people lose marks. Some innocent-looking method calls are themselves loops, and calling one inside your loop quietly makes your solution quadratic.

A one-line change from linear to quadratic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27function countUniqueBad(list) {
  let steps = 0;
  const seen = [];
  for (const x of list) {
    // includes() scans the whole array: a loop hiding inside your loop.
    steps += seen.length + 1;
    if (!seen.includes(x)) seen.push(x);
  }
  return { unique: seen.length, steps };
}

function countUniqueGood(list) {
  let steps = 0;
  const seen = new Set();
  for (const x of list) {
    steps++;                        // Set.has is O(1) on average
    seen.add(x);
  }
  return { unique: seen.size, steps };
}

for (const n of [100, 400, 800]) {
  const list = Array.from({ length: n }, (_, i) => i);
  console.log('n =', String(n).padStart(3),
    '| array + includes:', String(countUniqueBad(list).steps).padStart(7),
    '| Set:', countUniqueGood(list).steps);
}

Output

Same output, wildly different cost. Keep a list of the methods that hide a loop:

arr.includes, arr.indexOf, arr.find, arr.filter — O(n)
arr.unshift, arr.shift, arr.splice — O(n), because everything after the change point moves
arr.sort — O(n log n)
str + str in a loop — builds a new string each time
arr.slice, spreading [...arr], Object.keys — O(n)

And the ones that are genuinely cheap: arr[i], arr.push, arr.pop, map.get, map.set, set.has.

Space complexity

The same notation, applied to memory instead of time: how much extra space do you allocate as the input grows? The input itself does not count; what you add does.

The same job, O(1) space and O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16function sumInPlace(list) {
  let total = 0;              // one number, whatever the input size → O(1) space
  for (const x of list) total += x;
  return total;
}

function sumWithCopy(list) {
  const doubled = list.map(x => x * 2);   // a new array as big as the input → O(n) space
  let total = 0;
  for (const x of doubled) total += x;
  return total;
}

const list = [1, 2, 3, 4, 5];
console.log('in place:', sumInPlace(list), '— O(1) extra space');
console.log('with copy:', sumWithCopy(list), '— O(n) extra space');

Output

Depth is space: watch the stack grow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17function depth(n, level = 1) {
  if (n === 0) return level;
  return depth(n - 1, level + 1);   // one stack frame per call
}

console.log('deepest level for n=5:', depth(5));

// Go deep enough and the stack runs out. This is a real limit, not a theory.
function blowUp(n) {
  try {
    return blowUp(n + 1);
  } catch (err) {
    return { name: err.name, depthReached: n };
  }
}
const result = blowUp(0);
console.log('the stack ran out at roughly', result.depthReached, 'frames:', result.name);

Output

Amortized: why push is O(1)

An array has to live in a fixed block of memory. So what happens when you push onto a full one? The engine allocates a bigger block and copies everything across, which is O(n).

That sounds like push is O(n). It is not, because the engine doubles the capacity rather than adding one slot. So the expensive copy happens rarely, and if you average the cost over many pushes it comes out constant. We call that amortized O(1).

Doubling makes the average cost constant

1
2
3
4
5
6
7
8
9
10
11
12
13
14// A toy array that only grows by doubling, counting the copies it does.
function simulate(pushes) {
  let capacity = 1, size = 0, copies = 0;
  for (let i = 0; i < pushes; i++) {
    if (size === capacity) {       // full: allocate double and copy across
      copies += size;
      capacity *= 2;
    }
    size++;
  }
  return { pushes, copies, copiesPerPush: (copies / pushes).toFixed(2) };
}

for (const n of [10, 100, 1000, 100000]) console.log(simulate(n));

Output

Copies per push settles just under 1 and stays there however large the input gets. The work per operation is bounded by a constant on average, which is exactly what amortized O(1) means.

Reading complexity out loud

A method that works under pressure. For any function, ask four questions in order:

What is n? Name it. The length of the array, the number of nodes, the number of characters. If there are two inputs, you have n and m.
What is the innermost repeated line, and how many times does it run? That is your time complexity.
Does any call inside the loop hide a loop of its own? Multiply if so.
What did I allocate, and how deep does the recursion go? That is your space complexity.

Four functions. Say the complexity before you run it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17const a = (arr) => arr[0];

const b = (arr) => { let s = 0; for (const x of arr) s += x; return s; };

const c = (arr) => {
  const pairs = [];
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++) pairs.push([arr[i], arr[j]]);
  return pairs.length;
};

const d = (arr) => { const copy = [...arr].sort((x, y) => x - y); return copy[0]; };

console.log('a:', a([3, 1, 2]), '→ O(1) time, O(1) space');
console.log('b:', b([3, 1, 2]), '→ O(n) time, O(1) space');
console.log('c:', c([3, 1, 2]), '→ O(n^2) time, O(n^2) space (it stores every pair)');
console.log('d:', d([3, 1, 2]), '→ O(n log n) time, O(n) space (the copy)');

Output

Your turn: name the complexity

Five functions below. For each, write the time and space complexity in the comment before you run it. Then run it and compare with the step counts. Getting one wrong here is worth more than getting five right by guessing.

Editable. Fill in your answers, then run.

// 1. time: ______  space: ______
function f1(arr) {
  return arr.length > 0 ? arr[arr.length - 1] : null;
}

// 2. time: ______  space: ______
function f2(arr) {
  const out = [];
  for (const x of arr) if (x % 2 === 0) out.push(x);
  return out;
}

// 3. time: ______  space: ______
function f3(a, b) {
  let count = 0;
  for (const x of a) for (const y of b) if (x === y) count++;
  return count;
}

// 4. time: ______  space: ______
function f4(arr) {
  let n = arr.length, steps = 0;
  while (n > 1) { n = Math.floor(n / 2); steps++; }
  return steps;
}

// 5. time: ______  space: ______
function f5(arr) {
  const seen = new Set();
  for (const x of arr) { if (seen.has(x)) return true; seen.add(x); }
  return false;
}

console.log(f1([1, 2, 3]), f2([1, 2, 3, 4]), f3([1, 2], [2, 3]), f4(new Array(64)), f5([1, 2, 1]));

// Answers: 1) O(1)/O(1)  2) O(n)/O(n)  3) O(n*m)/O(1)  4) O(log n)/O(1)  5) O(n)/O(n)

Output

Recap

Big-O describes how work grows with input size, not how many milliseconds something takes.
Count the innermost repeated line. Sequential loops add; nested loops multiply.
Drop constants and keep only the largest term: O(3n² + n) is O(n²).
Methods like includes, indexOf, splice and shift are loops in disguise; calling one inside a loop makes you quadratic.
Space is extra memory plus recursion depth, and push is amortized O(1) because arrays grow by doubling.

Counting, not timing

The ladder

Two simplifications that always apply

The hidden loops

Space complexity

Amortized: why push is O(1)

Reading complexity out loud

Your turn: name the complexity

Recap

New writing, when it lands.