Languages · JavaScript

Time and Space Complexity

Big-O notation describes how an algorithm's running time (or memory use) grows as input size (n) grows — not the exact time in seconds, which depends on hardware. It answers: "if I double the input, roughly how much slower does this get?"

💻 Languages● Intermediate⏱ 8 min read🛠️ 3 exercises🎤 5 interview Q&As

🎯 What you'll learn

What Big-O Measures
The Common Complexity Classes, Fastest to Slowest
Why Constants and Lower-Order Terms Are Dropped
Nested Loops Multiply, Sequential Loops Add
Analyzing Real Array Method Costs

Part 1Big-O Notation

1What Big-O Measures

Big-O notation describes how an algorithm's running time (or memory use) grows as input size (n) grows — not the exact time in seconds, which depends on hardware. It answers: "if I double the input, roughly how much slower does this get?"

2The Common Complexity Classes, Fastest to Slowest

Growth curves from flattest to steepest: O(1), O(log n), O(n), O(n log n), O(n squared)

Notation	Name	Example	Doubling `n` roughly...
O(1)	constant	`arr[0]`, `map.get(key)`	...changes nothing
O(log n)	logarithmic	binary search	...adds one more step
O(n)	linear	a single loop over the array	...doubles the time
O(n log n)	linearithmic	efficient sorting (`Array.sort`)	...slightly more than doubles
O(n²)	quadratic	nested loop over the same array	...quadruples the time
O(2ⁿ)	exponential	naive recursive Fibonacci	...squares the time

function constant(arr) { return arr[0]; }                    // O(1)

function linear(arr) { for (const x of arr) console.log(x); } // O(n)

function quadratic(arr) {                                      // O(n²)
  for (const a of arr) for (const b of arr) console.log(a, b);
}

3Why Constants and Lower-Order Terms Are Dropped

function example(arr) {
  console.log(arr[0]);       // O(1)
  for (const x of arr) {}    // O(n)
  for (const x of arr) {}    // O(n) — a second, separate loop
}
// Total: O(1) + O(n) + O(n) = O(2n + 1)
// Big-O drops constants and lower-order terms -> simplifies to O(n)

Big-O describes growth trend, not an exact operation count — O(2n) and O(n) belong to the same complexity class because they scale identically as n → ∞.

4Nested Loops Multiply, Sequential Loops Add

function nested(arr) {          // O(n * n) = O(n²) — loops MULTIPLY when nested
  for (const a of arr) for (const b of arr) {}
}

function sequential(arr) {       // O(n + n) = O(n) — loops ADD when sequential, simplifies away
  for (const a of arr) {}
  for (const b of arr) {}
}

5Analyzing Real Array Method Costs

Operation	Complexity	Why
`arr[i]` (index access)	O(1)	direct memory offset
`arr.push()` / `arr.pop()`	O(1) amortized	operates at the end only
`arr.shift()` / `arr.unshift()`	O(n)	every remaining element must shift index
`arr.includes()` / `arr.indexOf()`	O(n)	must scan until found (or not)
`arr.sort()`	O(n log n)	comparison-based sort
`map.get(key)` / `set.has(value)`	O(1) average	hash table lookup (see Hashing topic)

const arr = [1, 2, 3, /* ...huge array... */];
arr.unshift(0); // O(n) — every other element's index shifts up by one, internally
arr.push(0);     // O(1) — no shifting needed, just appends at the end

Part 2Space Complexity and Trade-offs

1What Space Complexity Measures

Space complexity describes how much extra memory an algorithm needs, relative to input size — beyond the input itself. It uses the same Big-O notation as time complexity.

function sumArray(arr) {         // O(1) space — one accumulator variable, regardless of arr's size
  let total = 0;
  for (const n of arr) total += n;
  return total;
}

function doubleAll(arr) {         // O(n) space — allocates a NEW array of the same size
  return arr.map(n => n * 2);
}

function doubleInPlace(arr) {      // O(1) space — mutates the existing array, no new allocation
  for (let i = 0; i < arr.length; i++) arr[i] *= 2;
  return arr;
}

2The Classic Time-Space Trade-off

Using extra memory (space) can often reduce time complexity, and vice versa — this trade-off shows up constantly in real algorithm design.

// O(n²) time, O(1) extra space — checks every pair
function hasDuplicateSlow(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(n) time, O(n) extra space — trades memory (a Set) for speed
function hasDuplicateFast(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

This exact trade-off is the reasoning behind the Hashing topic's hash tables: spend O(n) extra memory to turn O(n) lookups into O(1) lookups.

3Recursive Functions and Call Stack Space

Every recursive call adds a frame to the call stack — recursive algorithms have space complexity proportional to their maximum recursion depth, not just their data structures.

function sumRecursive(arr, i = 0) {  // O(n) time, O(n) SPACE — n stack frames deep at the worst point
  if (i >= arr.length) return 0;
  return arr[i] + sumRecursive(arr, i + 1);
}

function sumIterative(arr) {          // O(n) time, O(1) space — no growing call stack
  let total = 0;
  for (const n of arr) total += n;
  return total;
}

A deep enough recursive call (tens of thousands of frames on a large array) can throw RangeError: Maximum call stack size exceeded — this is a direct, practical consequence of recursion's O(depth) space cost.

4Worked Example: Analyzing a Real Function

function findPairsSummingTo(arr, target) {
  const seen = new Set();          // O(n) space, worst case
  const pairs = [];                // O(n) space, worst case
  for (const num of arr) {          // O(n) time — single pass
    const complement = target - num;
    if (seen.has(complement)) pairs.push([complement, num]); // O(1) average lookup
    seen.add(num);                  // O(1) average insert
  }
  return pairs;
}
// Total: O(n) time, O(n) space

Compare this to a naive nested-loop version checking every pair: O(n²) time, O(1) extra space — the same time-space trade-off from section 2, applied to a real problem (this is exactly the "two sum" pattern from the Hashing topic's exercises).

Under the HoodWhy Real-World Constants Don't Match the Theory▾

Big-O deliberately ignores constant factors — but those constants come from somewhere real: the engine internals covered throughout this course. Two pieces of code with identical Big-O can have wildly different real-world speed because of them.

function sumMonomorphic(items) {          // every call site sees the SAME shape (Prototypes topic)
  let total = 0;
  for (const item of items) total += item.value; // monomorphic IC — near-free property read
  return total;
}

function sumMegamorphic(items) {           // items mix many different object shapes
  let total = 0;
  for (const item of items) total += item.value; // megamorphic IC — falls back to slow lookup
  return total;
}

Both functions are O(n) by the formal definition — same number of operations relative to input size. But sumMegamorphic, given an array whose objects don't share a hidden class, pays a real, measurable constant-factor penalty on every iteration from losing the inline-cache fast path (Prototype Chain topic) — sometimes several times slower in practice, despite having "the same" complexity on paper.

Elements kind matters for the same reason

[1, 2, 3].reduce((a, b) => a + b);              // PACKED_SMI_ELEMENTS — flat buffer, fast path
[1, "2", 3].reduce((a, b) => a + b);              // PACKED_ELEMENTS — generic tagged values, slower path

Both are O(n) traversals; the Arrays topic's elements-kind ladder means the actual per-element cost differs by a real constant factor depending on what's actually stored, not just how many elements there are.

The honest takeaway

Big-O tells you how an algorithm scales — it remains the right first tool for comparing fundamentally different approaches (O(n²) vs O(n log n) will always lose for large enough n, regardless of engine tricks). But within the same complexity class, the JIT/hidden-class/elements-kind machinery from earlier topics determines the real constant factor — which is why "this is O(n) so it should be fast" sometimes doesn't hold up under actual profiling, and why consistent object shapes and array contents matter for performance even when they don't change an algorithm's asymptotic classification at all.

⚠️ Common Pitfalls

Confusing "fewer lines of code" with "faster" — a one-line .includes() inside a loop can hide an O(n) scan, turning an apparently simple loop into accidental O(n²).
Ignoring space complexity entirely — an O(n) time solution that also needs O(n²) space might be worse in practice than a slightly slower solution that fits in memory.
Not accounting for recursion's stack space — assuming a recursive solution is "free" because it looks concise, when it may add O(n) stack depth a loop-based version wouldn't need.
Big-O ≠ actual speed for small n — an O(n²) algorithm can outperform an O(n log n) one for very small inputs, due to lower constant overhead; Big-O only describes behavior as n grows large.

📋 Quick Reference

text

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
nested loops → multiply     sequential loops → add (then simplify)
extra data structure → often trades space for time
recursion depth → counts as space complexity

🎤 Interview Q&A

Questions interviewers ask about this topic. Answer out loud first, then open a card to compare.

Q1What is Big-O notation?core▾

It describes how running time or memory grows with input size, keeping the dominant term and dropping constants: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n).

Follow-ups interviewers ask

Best/average/worst case? Big-O usually refers to the worst case unless stated.

Q2What are the complexities of common JavaScript operations?core▾

Array index/push/pop O(1); shift/unshift/splice O(n); includes/indexOf O(n); sort O(n log n); Map/Set get/set/has O(1) average; object property access O(1) average; string concatenation in loops can be O(n²) in naive cases.

Follow-ups interviewers ask

Why is shift O(n)? Elements must be re-indexed.

Q3How do you analyze space complexity?core▾

Count additional memory relative to input: new arrays/maps, recursion depth (call stack), and copies. Spreading arrays in loops or recursion can silently add O(n) or O(n²) memory.

Follow-ups interviewers ask

Recursion space? O(depth) for the call stack.

Q4What's amortized complexity?senior▾

Average cost per operation over a sequence, e.g. dynamic array push is O(1) amortized even though occasional resizes are O(n).

Follow-ups interviewers ask

Another example? Hash table inserts with resizing.

Q5Does Big-O tell the whole performance story?core▾

No; constants, memory locality, allocation/GC pressure and input sizes matter. For small n, a simple O(n²) loop can beat a complex O(n log n) approach. Measure for real performance.

Follow-ups interviewers ask

Tool? Benchmarks and profilers.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

#1 · .js

classify the time complexity of each function

js_time_and_space_complexity_exercise_1.js

#2 · .js

optimize an O(n^2) function to O(n) using extra space

js_time_and_space_complexity_exercise_2.js

#3 · .js

convert an O(n) space recursive function to O(1) space iterative

js_time_and_space_complexity_exercise_3.js

Source: js_time_and_space_complexity_theory_1.md, js_time_and_space_complexity_theory_2.md · generated by tools/build_lessons.py