Foundations: measuring code · Lesson 2 of 23
Space and the time–memory trade-off
How much memory a solution uses, and when to spend memory to save time.
Besides steps, we count the extra memory a solution needs beyond the input. A Set of every element is O(n) space; a handful of variables is O(1).
In many problems we can buy time with memory: store something in a Map so it's never recomputed.
// Pair sum: two indexes whose values add up to target
// Version 1: O(n²) time, O(1) space
function pairSlow(nums, target) {
for (let i = 0; i < nums.length; i++)
for (let j = i + 1; j < nums.length; j++)
if (nums[i] + nums[j] === target) return [i, j]
return []
}
// Version 2: O(n) time, O(n) space — remember what we've seen
function pairFast(nums, target) {
const where = new Map()
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i]
if (where.has(need)) return [where.get(need), i]
where.set(nums[i], i)
}
return []
}
console.log(pairSlow([2, 7, 11, 15], 9), pairFast([2, 7, 11, 15], 9))| Solution | Time | Space | When to choose it |
|---|---|---|---|
pairSlow | O(n²) | O(1) | Very tight memory and small n |
pairFast | O(n) | O(n) | Almost always |
Sort + two pointers | O(n log n) | O(1)–O(n) | When original indexes don't matter |
Recursion uses memory too
Every function call holds a slot on the call stack until it returns. A recursive function that goes n levels deep uses O(n) memory even without building arrays, which is why large inputs can hit "Maximum call stack size exceeded".
Quick question
A function builds a new array of the squares of all numbers. Its extra space?
Spot the bug
This should sum 1 + 2 + … + n, but crashes when n = 100000. Which line is the cause?
Exercise
Write sumTo(n) with a plain loop (O(1) memory) instead of recursion. It must print 5000050000.
Expected output: 5000050000
function sumTo(n) {
}
console.log(sumTo(100000))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 3 games
Sign in to save your progress and earn XP.