Complexity Analysis for JS Engineers

Big-O for frontend interviews — arrays, maps, DOM work, and how to talk complexity when the bottleneck is the main thread.

beginner4 min readUpdated Aug 4, 2026

interview
complexity-analysis

Frontend engineers still get asked “what’s the complexity?” — in DSA rounds and when you filter 50k rows in the browser. You need asymptotic intuition plus honesty about constants, GC, and layout.

What “good enough” means in interviews

State time and space for your solution
Name the dominant term as input grows
Compare brute vs improved clearly
For UI: mention main-thread cost and when to virtualize

You do not need a math degree. You need not to ship O(n²) by accident and claim it’s fine.

Core table (memorize via use)

Structure / op	Average	Notes in JS
Array index read/write	O(1)	Contiguous; sparse arrays are weird
Array `push` / `pop`	O(1) amortized	`unshift` / `shift` are O(n)
Array `includes` / `indexOf`	O(n)	Prefer `Set` for membership
Object key access	O(1) avg	String/symbol keys
`Map` / `Set` ops	O(1) avg	Better for frequent add/delete
Sort	O(n log n)	`Array.prototype.sort`
Deep clone naive	O(n) nodes	Cycles; prefer structuredClone when OK

Worked micro-examples

Membership: array vs Set

// O(n * m) if check is array.includes inside loop
function uniqueCountSlow(items, universe) {
  let count = 0;
  for (const x of items) {
    if (universe.includes(x)) count++; // O(m) each
  }
  return count;
}

// O(n + m)
function uniqueCountFast(items, universe) {
  const set = new Set(universe); // O(m)
  let count = 0;
  for (const x of items) {
    if (set.has(x)) count++; // O(1) avg
  }
  return count;
}

Nested loops on UI data

// O(n²) — fine for n=20, death for n=5_000
function relatedPosts(posts) {
  return posts.map((p) => ({
    ...p,
    related: posts.filter((q) => q.tag === p.tag && q.id !== p.id),
  }));
}

// O(n) group then O(n)
function relatedPostsFast(posts) {
  const byTag = new Map();
  for (const p of posts) {
    if (!byTag.has(p.tag)) byTag.set(p.tag, []);
    byTag.get(p.tag).push(p);
  }
  return posts.map((p) => ({
    ...p,
    related: (byTag.get(p.tag) || []).filter((q) => q.id !== p.id),
  }));
}

Say out loud: “Same output shape; we traded a second pass for avoiding quadratic filters.”

Complexity + frontend reality

Work	Asymptotic	Constant factors that dominate
Diffing list of n rows	O(n)	Component cost per row
Layout thrash n reads/writes	O(n)	Each forces style/layout
JSON.parse large payload	O(n)	Main-thread block
Canvas draw n sprites	O(n)	GPU/fill rate
Regex catastrophic backtracking	exponential	Input-dependent footgun

For lists, list virtualization keeps DOM nodes ~constant while data is O(n). Complexity of data vs DOM is a senior talking point.

How to answer in a DSA-style FE round

Template:

Brute: O(n²) time, O(1) extra space — explain
Better: Hash map → O(n) time, O(n) space
Why trade space: interview n up to 10⁵; quadratic times out
Edge cases: empty, duplicates, negative numbers

Classic: Two sum — brute nested loops vs map of complements.

// O(n) time, O(n) space
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}

Amortized & average case (say carefully)

Amortized O(1) push: occasional resize O(n), rare enough
Hash O(1) average: pathological collisions exist; rare in V8 for normal keys
Sort O(n log n): engines use efficient hybrids; still don’t sort every keystroke without debounce

Space complexity footguns

Closures retaining large arrays (memory leak “soft”)
Growing Map caches without eviction — mention LRU: LRU cache
Spreading huge objects each render

Out-loud one-liners

Q: Why is shift O(n)?
“It renumbers every index after 0.”

Q: Is React O(n) per setState?
“React walks the updated subtree; cost scales with work in that tree, not always the whole app. Memoization changes constants, not magic O(1).”

Q: Big-O of querySelectorAll?
“Typically linear in document size for full scans; be careful in hot paths.”

Practice set

State complexity for debounce leading/trailing (not just “O(1)”).
Analyze flatten nested arrays (depth vs width).
Event emitter: subscribe/emit costs with many listeners.
Virtual list: complexity of scroll handler vs full render.

Patterns: JavaScript coding interview patterns.