Big O and Complexity
Time vs Space Complexity
Written by Swapnil RajaPublished
Almost every optimisation in this tutorial is the same move: use more memory so you do less work. Knowing what you are spending is how you tell a good trade from a bad one.
Two different costs
Time complexity counts operations as the input grows. Space complexity counts extra memory, not counting the input itself.
The input does not count because you were given it. What counts is what you allocate on top.
Same result, different space
javascript
// O(1) space — one accumulator, however big the input.
function sum(items) {
let total = 0
for (const n of items) total += n
return total
}
// O(n) space — a new array as large as the input.
function doubled(items) {
return items.map((n) => n * 2)
}
// O(n) space, and the reason we accept it.
function firstDuplicate(items) {
const seen = new Set()
for (const n of items) {
if (seen.has(n)) return n
seen.add(n)
}
return null
}