Complexity analysis

What Big-O actually measures

Big-O is not a speed measurement. It's a description of how the work grows as the input grows. Two functions can both be "O(n)" and one can be 100x slower than the other in real seconds — Big-O doesn't care. It only answers one question: if you double the input, roughly what happens to the work?

The formal definition — worth seeing once

You'll almost never need to write this out in an interview, but knowing it makes every informal explanation click into place. Formally, f(n) = O(g(n)) means: there exist positive constants c and n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀. In plain words — past some point, f(n) never grows faster than a constant multiple of g(n). Big-O is an upper bound on growth, not an exact count.

This is exactly why constants get dropped: f(n) = 5n is still O(n), because you can always pick a big enough c (say, c = 5) to make the inequality true. Big-O cares about the shape as n → ∞, not the specific multiplier.

Big-O's two siblings: Ω and Θ

Big-O gets all the attention in interviews, but it's technically only the upper bound. Two related notations describe the other directions — worth being able to name if asked "isn't that also Ω(something)?"

Example: linear search is O(n) (never worse than scanning everything) and Ω(1) (you might get lucky and find it first) — so it's not Θ(n) in general, because best and worst case differ. Merge sort, on the other hand, always does Θ(n log n) — best, average and worst case are all the same shape, so people often say "O(n log n)" and "Θ(n log n)" almost interchangeably for it. In interviews, saying "O" when you technically mean "Θ" is common and accepted — but knowing the difference exists signals real understanding.

Best, average, and worst case — three different questions

"What's the complexity of X" is actually an incomplete question — the answer can depend on which input you're worried about.

Unless told otherwise, interviewers want the worst case — it's the guarantee that holds no matter what input shows up. But naming the best case too (especially when it differs a lot, like quicksort's) shows you actually understand the algorithm's behavior instead of having memorized one number.

Multiple inputs — when there isn't just one "n"

Plenty of real problems take two different collections, and it's a common mistake to collapse them into one variable when they shouldn't be. If a function has an array of size a and a second array of size b:

// O(a + b) — two SEPARATE passes, not nested
function concat(arr1, arr2) {
  const result = [];
  for (const x of arr1) result.push(x);  // O(a)
  for (const x of arr2) result.push(x);  // O(b)
  return result;
}

// O(a × b) — NESTED, every element of one meets every element of the other
function hasCommonElement(arr1, arr2) {
  for (const x of arr1) {
    for (const y of arr2) {
      if (x === y) return true;
    }
  }
  return false;
}

The picture that makes it click

Every explanation of Big-O eventually points at the same chart. Look at it once, properly, and the notation stops being abstract letters and starts being a shape you recognize on sight.

Why the shape matters more than it seems — actual numbers

The chart makes the shape obvious, but the real gut-punch is what these shapes mean at realistic input sizes. This is the table that explains why an interviewer's face changes when your solution is O(n²) on an input that might be a million elements.

A modern CPU does roughly 10⁸–10⁹ simple operations per second. At n = 1,000,000, an O(n) solution finishes in a blink; an O(n²) solution needs a trillion operations — that's minutes to hours, not milliseconds, on the exact same input. This is the entire reason interviewers care so much about the shape and so little about your variable names.

The complexities you'll actually see

In interviews, almost every answer you'll ever give is one of these seven. If you can name which shape your solution is and defend why, you've already cleared the bar most candidates trip on.

Reading complexity out of code

The rule of thumb: count the loops, not the lines.

// O(1) — no loop, fixed number of steps
function first(arr) {
  return arr[0];
}

// O(n) — one loop over the input
function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  return total;
}

// O(n²) — a loop inside a loop, both sized by n
function hasDuplicatePair(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// O(log n) — the search space halves every step
function binarySearch(sorted, target) {
  let lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// looks like O(n) — is actually O(n²)
function hasDuplicate(arr) {
  const seen = [];
  for (const x of arr) {
    if (seen.includes(x)) return true;  // O(n) work, n times
    seen.push(x);
  }
  return false;
}

// the fix: swap the array for a Set → O(1) lookup → true O(n)
function hasDuplicateFast(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Dry run: hasDuplicate([3, 1, 4, 1]) — counting the hidden work

0 + 1 + 2 + 2 = 5 comparisons to check an array of only 4 elements — the cost of each includes call grows with how much of seen exists so far, not a fixed amount. That growing-per- iteration cost is the O(n²) signature hiding behind what reads like a single, innocent for...of loop.

Loops that don't count up by one

"Count the loops" works when every loop runs n times. Plenty of loops don't: the variable doubles, the inner loop starts where the outer one is, the condition tests i * i. For all of these the honest method is one question, asked of each loop in turn: how many times does the body run, as a function of n? The five shapes below cover almost everything you will meet. Each function counts its own body, so the table afterwards is measured, not guessed.

function countDoubling(n) {
  let steps = 0;
  for (let i = 1; i < n; i *= 2) steps++;
  return steps;
}

function countTriangle(n) {
  let steps = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) steps++;
  }
  return steps;
}

function countSqrt(n) {
  let steps = 0;
  for (let i = 2; i * i <= n; i++) steps++;
  return steps;
}

function countHarmonic(n) {
  let steps = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = i; j <= n; j += i) steps++;
  }
  return steps;
}

function countNestedDoubling(n) {
  let steps = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < n; j *= 2) steps++;
  }
  return steps;
}

Read the columns against the n that produced them and the shapes appear. Here is where each one comes from.

• Doubling is logarithmic. i takes the values 1, 2, 4, 8, ..., 2^k−1 and stops once 2^k reaches n. So the body runs ⌈log₂ n⌉ times: 10 times for n = 1,000, 20 for a million, and only 30 for a billion. Halving (n = Math.floor(n / 2) until it hits 0) is the same loop run backwards, which is exactly why binary search is O(log n).
• A dependent inner loop is quadratic, with a half in front. When the outer variable is i, the inner loop runs n − 1 − i times, so the total is (n−1) + (n−2) + ... + 1 + 0 = n(n−1)/2. For n = 5 that is 4 + 3 + 2 + 1 + 0 = 10. The ½ is a constant, so the class is still O(n²): halving the work of a quadratic loop does not make it a different shape.
• A condition on i * i is a square root. i * i <= n is the same test as i <= √n, so the loop runs about √n times. Trial division for primality stops there because if n = a · b with a ≤ b, then a ≤ √n: any factor pair has a member at or below the root. A million costs about a thousand steps.
• A stride that grows with i is harmonic. The inner loop of countHarmonic runs ⌊n/i⌋ times, so the total is n · (1 + ½ + ⅓ + ... + 1/n) ≈ n · ln n. It is not n² because most values of i are large and their inner loop runs only a few times; for n = 100 the exact count is 482, close to 100 · ln 100 ≈ 460. This is the shape of the sieve of Eratosthenes, though the real sieve only strides from primes, which brings it down to O(n log log n).
• A linear loop around a logarithmic one multiplies. countNestedDoubling runs n times a loop that runs log n times: O(n log n), and the table shows exactly n × ⌈log₂ n⌉ (1,000 × 10 = 10,000).

One more shape matters a great deal for the next chapters: a loop inside a loop whose inner variable does not reset. This is the engine of every two-pointer and sliding-window solution.

function countWindowMoves(nums, limit) {
  let left = 0, sum = 0, moves = 0;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    moves++;
    while (sum > limit && left <= right) {
      sum -= nums[left];
      left++;
      moves++;
    }
  }
  return moves;
}

It has a while inside a for, and it is O(n), not O(n²). left never moves backwards and never passes right + 1, so across the whole run it advances at most n times in total. right advances n times. The inner loop does not restart from zero on every outer step, so the two loops share a budget of at most 2n moves instead of multiplying. For countWindowMoves([4, 2, 3, 5, 1], 6) the moves are 5 steps of right plus 3 of left, 8 in all, well under 2n = 10.

What built-in calls really cost

Most hidden quadratics come from one line that looks like a single step but is a loop inside the engine. The language specification does not promise any of these costs, and an engine is free to be faster than the table, but this is what to assume in an interview and say out loud. Read the right-hand column as "the work this line is allowed to hide".

Two rows deserve a second look. The callback row is where most accidental quadratics are born: arr.filter((x) => other.includes(x)) is one line and O(n × m), because the callback's includes scans other for every element. And the string-key row is the polite lie of hash maps: a map of n strings, each of length L, costs O(n · L) to fill, not O(n), because every key has to be hashed character by character. When the strings are short that is a constant, and when the interviewer says "each word can be up to 10,000 characters", it is not.

Here is the table at work on a short function. Read it line by line, the way you would out loud.

function lengthsReversed(words) {          // n words, each up to L characters
  const sorted = [...words].sort();         // spread O(n); sort O(n log n) compares, each up to O(L)
  const out = [];
  for (const w of sorted) {                 // n iterations
    out.unshift(w.length);                  // O(n) every time: the hidden loop
  }
  return out;
}

Which term wins depends on the input: with short words the quadratic unshift loop dominates, and with a few very long words the sort does. Naming both terms instead of rounding to one is what shows the interviewer you looked inside the lines. The fix for the loop is to push and reverse once at the end, which is O(n).

Dropping constants and lower-order terms

O(2n) is written as O(n). O(n² + n) is written as O(n²). Big-O describes what dominates as n gets large — the constant factor and the smaller terms stop mattering. This is also why "my solution does 3 passes instead of 1" is still O(n), just with a bigger constant. It's a legitimate follow-up question ("can you get it to one pass?") but it doesn't change the Big-O class.

Recurrence relations — how you actually derive O(n log n)

For recursive code, "count the loops" doesn't work — you need a recurrence relation: an equation describing the work at size n in terms of the work at smaller sizes. Merge sort's recurrence is the classic example:

T(n) = 2·T(n/2) + O(n)
       ↑           ↑
       2 subproblems   the merge step, linear work
       of half the size

Read it as: "the cost of sorting n elements equals the cost of sorting two halves, plus the linear-time work to merge them back together." Solving this (formally, by repeatedly substituting, or informally with the recursion-tree diagram from the sorting chapter — each of log n levels does O(n) total work) gives T(n) = O(n log n).

You will not be asked to apply the Master Theorem from memory in most interviews — but being able to write down a recurrence for your own recursive solution, and reason informally about "how many levels × how much work per level," is a real and commonly-tested skill.

Memoized recursion: states times work per state

A recurrence like T(n) = T(n−1) + T(n−2) + O(1) counts calls, and it is the right tool for plain recursion. Add a cache and it stops being the right tool, because most of those calls no longer do anything. The count that matters changes to this:

Watch the rule on Fibonacci, counting both the calls and the bodies that actually run.

function fibNaive(n, stats) {
  stats.calls++;
  if (n < 2) return n;
  return fibNaive(n - 1, stats) + fibNaive(n - 2, stats);
}

function fibMemo(n, stats, memo = new Map()) {
  stats.calls++;
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  stats.bodies++;
  const value = fibMemo(n - 1, stats, memo) + fibMemo(n - 2, stats, memo);
  memo.set(n, value);
  return value;
}

There are n − 1 states that run a body (the values 2 through n), and each body does O(1) work besides its two recursive calls, so the time is O(n). The calls column is about twice the bodies column because every body makes two calls and only the first call into a state does real work. That is the general shape: calls ≤ states × calls per body, so counting bodies loses at most a constant factor.

The rule matters most when the work per state is not constant. Minimum coins to make an amount is the standard example:

function minCoins(coins, amount) {
  const memo = new Map();
  function solve(left) {
    if (left === 0) return 0;
    if (left < 0) return Infinity;
    if (memo.has(left)) return memo.get(left);
    let best = Infinity;
    for (const coin of coins) {
      best = Math.min(best, solve(left - coin) + 1);
    }
    memo.set(left, best);
    return best;
  }
  const result = solve(amount);
  return result === Infinity ? -1 : result;
}

With coins = [1, 2, 5] and an amount of 11, 100 or 1,000, the count of bodies run is exactly 11, 100 and 1,000: one per amount, as the table says. Without the cache the same recursion branches three ways at every level and its call tree grows exponentially in the amount.

The same rule prices every DP you will write later: a table of r × c cells with O(1) work per cell is O(r · c); a table of n cells where each looks back over all earlier cells is O(n²). See DP in one dimension for the full treatment.

Space complexity — the part people forget

Space complexity counts extra memory your algorithm uses, not counting the input itself. Two things people forget to count:

• Output that isn't asked for as input — building a new array to return costs O(n) space, even if you never call new Array() explicitly.
• The call stack. Recursion isn't free — each call frame sits on the stack until it returns. A recursive function that goes n levels deep costs O(n) space even if it allocates nothing else.

// O(n) time, O(1) space — no extra structure grows with input
function maxValue(arr) {
  let max = -Infinity;
  for (const x of arr) if (x > max) max = x;
  return max;
}

// O(n) time, O(n) space — the call stack holds n frames
function sumRecursive(arr, i = 0) {
  if (i === arr.length) return 0;
  return arr[i] + sumRecursive(arr, i + 1);
}

Amortized complexity — the array.push() case

array.push() is described as O(1), but that's an amortized average, not a per-call guarantee. Under the hood a dynamic array is backed by a fixed-size buffer; most pushes are O(1), but occasionally the buffer is full and the engine allocates a new, bigger one and copies everything over — an O(n) operation. Because that expensive copy happens rarely (typically doubling the capacity each time), the average cost per push, spread over many calls, works out to O(1). "Amortized O(1)" means exactly this: not every single call is cheap, but the total cost over many calls divides out to a constant per call.

The potential method: amortized cost with a bank account

The aggregate method above works when you can add up the whole sequence at once. Many structures are easier to reason about one operation at a time, and for that you use a potential function Φ: a number computed from the structure's current state that stands for "work we have already paid for but not yet done". The amortized cost of an operation is its actual cost plus the change in potential:

amortized = actual + Φ(after) − Φ(before)

Add this up over a sequence of n operations and the Φ terms cancel from end to end, leaving total actual cost = total amortized cost − Φ(final) + Φ(start). So if Φ starts at 0 and never goes negative, the total actual cost is at most the total amortized cost. If every operation has a constant amortized cost, the whole sequence does too.

For the doubling array, pick Φ = 2 · size − capacity. Then the argument has only two cases:

• A push with room to spare. Actual cost 1. The size grows by one, so Φ rises by 2. Amortized = 1 + 2 = 3.
• A push into a full array (size = capacity = c). Actual cost c + 1: copy the c elements, then write one. Before the push Φ = 2c − c = c. Afterwards the size is c + 1 and the capacity is 2c, so Φ = 2(c + 1) − 2c = 2. Amortized = (c + 1) + (2 − c) = 3. The big copy is paid for by the potential the cheap pushes stored up.

So every push has amortized cost at most 3, and n pushes cost at most 3n in total. The code below replays the argument by running a model of the array and recording both numbers for every push.

function simulatePushes(n) {
  let size = 0, capacity = 0, actual = 0;
  const amortized = [];
  for (let k = 0; k < n; k++) {
    const before = 2 * size - capacity;
    let cost = 1;
    if (size === capacity) {
      cost += size;
      capacity = Math.max(1, capacity * 2);
    }
    size++;
    actual += cost;
    amortized.push(cost + (2 * size - capacity) - before);
  }
  return { actual, amortized };
}

Dry run: the first six pushes

Total actual cost of the first five pushes is 1 + 2 + 3 + 1 + 5 = 12, against a budget of 3 × 5 = 15. The expensive pushes (3 and 5) are exactly the ones where Φ drops. For n = 1,000 the simulation gives a total actual cost of 2,023 and a largest amortized value of 3. The first push shows 2 rather than 3 only because the model starts from capacity 0.

You will almost never write a potential function in an interview. What is worth having is the story it tells: every cheap operation pays a little extra into an account, and an occasional expensive one spends the account. That is how to defend "amortized O(1)" for a dynamic array, for the two-stack queue, and for a monotonic stack where each element is pushed once and popped at most once.

Output size, and numbers that are values rather than sizes

Two cases make "count the loops" give an answer that is right on paper and wrong in practice.

The output is part of the work. No algorithm can run faster than the time it takes to write its answer. A function that returns every subset of n numbers must produce 2ⁿ arrays whose lengths add up to n · 2ⁿ⁻¹, so it is Θ(n · 2ⁿ) however cleverly it is written.

function allSubsets(nums) {
  const out = [[]];
  for (const x of nums) {
    const size = out.length;
    for (let i = 0; i < size; i++) out.push([...out[i], x]);
  }
  return out;
}

Counting the work: the loop over nums runs n times, but the inner loop doubles each round (1, 2, 4, ..., 2ⁿ⁻¹ subsets), and each [...out[i], x] copies the subset it extends. For n = 10 the result has 1,024 subsets with 5,120 elements in total; for n = 20 it has 1,048,576 subsets and 10,485,760 elements. Say so out loud: "O(n · 2ⁿ), and that is also the size of the output, so it cannot be beaten". The same reasoning prices all permutations at O(n · n!) and all pairs at O(n²).

A number can be an input whose value is the loop bound. An algorithm is pseudo-polynomial when its cost is polynomial in the numeric value of an input but exponential in the number of digits it takes to write that input. The subset-sum check below is the classic case:

function canMakeSum(nums, target) {
  const reachable = new Uint8Array(target + 1);
  reachable[0] = 1;
  for (const x of nums) {
    for (let s = target; s >= x; s--) {
      if (reachable[s - x]) reachable[s] = 1;
    }
  }
  return reachable[target] === 1;
}

The time is O(n · target) and the space is O(target). It is "polynomial" only if you treat target as the input size. But adding one digit to the target multiplies the work by ten, so in terms of the length of the input it is exponential. The honest interview statement is "O(n · T) time and O(T) space, which is fine because T is at most a few thousand here". Two others you will meet: trial-division primality (for (let i = 2; i * i <= n; i++)) is O(√N) in the value N, about 31,621 steps for N = 1,000,000,007, and the 0/1 knapsack DP is O(n · W) in the capacity W.

The constraints tell you the target complexity

The most useful complexity skill in an interview happens before any code: read the limits on n and work backwards. A comfortable budget to plan for is about 10⁸ simple steps, which is a rule of thumb for choosing an approach, not a measurement. The table lists the largest growth rate that fits under that budget for each size of n, and the kind of solution that usually lives there.

Use it in two directions. Forward: when a problem says n ≤ 10⁵ and your first idea is an O(n²) pair loop (10¹⁰ steps), you know before writing a line that the idea is too slow and a hash map, sort, or pointer technique is needed. Backward: when the limit is n ≤ 20 and someone proposes a clever O(n) greedy, the small limit is a hint that the intended solution is an exponential search, and the greedy may be wrong. The sizes in the table also tell you what not to over-engineer: at n ≤ 1,000, an O(n²) loop is 10⁶ steps and a perfectly good answer.

// what's the time complexity of this function? try changing
// the input size in your head before running — does the pattern hold?
function countPairs(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] + arr[j] === 10) count++;
    }
  }
  return count;
}

console.log(countPairs([1, 9, 2, 8, 3, 7]));

Two nested loops, each running the full length of the array → O(n²) time, O(1) space. Notice it doesn't matter that the inner loop "only" checks a sum — the shape is decided by the loop structure, not what's inside it.