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 + hi) >> 1;
    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;
}

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.

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.

// 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.