Time Complexity vs Space Complexity

0/12 in this phase0/57 across the roadmap

📖 Concept

Time complexity measures how many operations an algorithm performs relative to input size. Space complexity measures how much additional memory it uses.

Why it matters: In real-world systems, you constantly trade time for space and vice versa. Caching (using more memory to save time), compression (using more time to save space), and hash tables (using extra space for O(1) lookups) are all time-space tradeoffs.

Time Complexity counts:

Loop iterations
Recursive calls
Function calls
Comparisons, assignments, arithmetic

Space Complexity counts:

Variables created
Data structures allocated
Recursive call stack depth
Temporary arrays/objects

The Time-Space Tradeoff:

Use a hash set to check duplicates: O(n) time + O(n) space vs O(n²) time + O(1) space
Memoize recursive results: O(n) time + O(n) space vs O(2ⁿ) time + O(n) space
Pre-compute prefix sums: O(1) per query + O(n) space vs O(n) per query + O(1) space

Auxiliary space vs Total space:

Auxiliary space = extra space used beyond the input (what we usually mean)
Total space = input space + auxiliary space

🏠 Real-world analogy: Time complexity is how long a trip takes. Space complexity is how much luggage you bring. A GPS (extra space) saves you time finding the route. A paper map (less space) takes more time but works offline.

💻 Code Example

codeTap to expand ⛶

1// Time: O(n), Space: O(1) — in-place
2function findMax(arr) {
3  let max = arr[0]; // O(1) extra space
4  for (let i = 1; i < arr.length; i++) {
5    if (arr[i] > max) max = arr[i];
6  }
7  return max;
8}
9
10// Time: O(n), Space: O(n) — extra array
11function reverseArray(arr) {
12  const result = []; // O(n) extra space
13  for (let i = arr.length - 1; i >= 0; i--) {
14    result.push(arr[i]);
15  }
16  return result;
17}
18
19// Time: O(1), Space: O(1) — in-place swap
20function reverseInPlace(arr) {
21  let left = 0, right = arr.length - 1;
22  while (left < right) {
23    [arr[left], arr[right]] = [arr[right], arr[left]];
24    left++;
25    right--;
26  }
27  return arr;
28}
29
30// Time-Space Tradeoff Example
31// Approach 1: O(n²) time, O(1) space
32function hasDuplicateBrute(arr) {
33  for (let i = 0; i < arr.length; i++) {
34    for (let j = i + 1; j < arr.length; j++) {
35      if (arr[i] === arr[j]) return true;
36    }
37  }
38  return false;
39}
40
41// Approach 2: O(n) time, O(n) space
42function hasDuplicateSet(arr) {
43  const seen = new Set();
44  for (const val of arr) {
45    if (seen.has(val)) return true;
46    seen.add(val);
47  }
48  return false;
49}
50
51// TypeScript — clearly typed tradeoff
52function hasDuplicateTS(arr: number[]): boolean {
53  const seen: Set<number> = new Set();
54  for (const val of arr) {
55    if (seen.has(val)) return true;
56    seen.add(val);
57  }
58  return false;
59}
60
61// Recursive space — call stack counts!
62function factorial(n) {
63  if (n <= 1) return 1;
64  return n * factorial(n - 1);
65  // Time: O(n), Space: O(n) ← call stack depth!
66}
67
68// Iterative version — saves stack space
69function factorialIterative(n) {
70  let result = 1;
71  for (let i = 2; i <= n; i++) result *= i;
72  return result;
73  // Time: O(n), Space: O(1) ← no call stack
74}

🏋️ Practice Exercise

Practice Problems:

Analyze time AND space for: creating a copy of an array
What's the space complexity of a recursive fibonacci(n)?
Rewrite arr.filter(x => x > 5) to be O(1) space (in-place)
Compare: sorting + binary search vs hash set for "contains" queries
A function creates a 2D matrix of size n×n. What's its space complexity?
What's the space complexity of merge sort vs quick sort?
You have 1GB RAM and need to process 10GB of data. Which complexity constraint matters more?
Write a function that checks if a string is a palindrome with O(1) extra space
Compare space usage: adjacency matrix vs adjacency list for a sparse graph
Design a solution where you trade O(n) space for O(1) lookup time

⚠️ Common Mistakes

Ignoring recursive call stack depth — each recursive call adds a frame to the stack, counting as O(depth) space
Forgetting that creating a new array/object inside a loop multiplies space usage
Thinking in-place always means O(1) space — in-place quicksort still uses O(log n) stack space
Not considering the space of the output — if you return a new array of size n, that's O(n) space
Confusing auxiliary space with total space — interviews usually ask about auxiliary (extra) space

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Time Complexity vs Space Complexity

Was this topic helpful?

← PreviousBig-O Notation & Complexity Analysis Next →Best / Worst / Average Case Analysis