Big O & Complexity

Big O describes how the work an algorithm does grows as the input grows. It ignores machine speed and constants and keeps only the shape of the growth. It is the vocabulary every other topic here uses.

Common growth ratesCopy Anchor Link

How to calculate itCopy Anchor Link

• Drop constants. 3n and n + 100 are both O(n).
• Keep the dominant term. n² + n is O(n²).
• Sequential steps add, nested steps multiply. Two loops one after the other: O(n + m). A loop inside a loop: O(n × m).
• Different inputs get different letters. Looping over a then over b is O(a + b), not O(n).
• Halving each step is log n. Anything that cuts the problem in half per step (binary search, balanced tree height) is O(log n).

Counting memory (space)Copy Anchor Link

Count the extra memory you allocate, including the recursion call stack. A recursive function that goes n calls deep uses O(n) stack space even if it allocates nothing else.

Best, average, worst, amortisedCopy Anchor Link

Big O usually means the worst case. Quicksort is O(n log n) on average and O(n²) in the worst case. Amortised cost averages over a sequence: array.push is occasionally O(n) when the array grows, but O(1) amortised.

Cost of common JavaScript operationsCopy Anchor Link

What the input size tells youCopy Anchor Link

Interview constraints hint at the target complexity.

CodeCopy Anchor Link

// One example per growth rate. `n` is the input size.

const constant = arr => arr[0]; // O(1)

function logarithmic(n) { // O(log n): halve until 1
  let steps = 0;
  while (n > 1) { n = Math.floor(n / 2); steps++; }
  return steps;
}

const linear = arr => arr.reduce((sum, x) => sum + x, 0); // O(n)

function quadratic(arr) { // O(n^2): every pair
  const pairs = [];
  for (const a of arr) for (const b of arr) pairs.push([a, b]);
  return pairs;
}

function subsets(arr) { // O(2^n): each item in or out
  return arr.reduce((all, x) => all.concat(all.map(s => [...s, x])), [[]]);
}

// Two inputs means two variables: O(a + b), not O(n).
const both = (a, b) => [...a.map(x => x * 2), ...b.map(x => x + 1)];

export { constant, logarithmic, linear, quadratic, subsets, both };