0
Challenge · 21Cost: Time and Space
Space complexity and the call stack
Complexityused in ~85% of apps
Every time you traded memory for speed, the Set, the Map, the counting object, you spent something. Here is what you spent, how to describe it, and the invisible memory that a function uses just by calling itself.
Core idea. Space complexity counts the extra memory your solution allocates, in terms of the input size. The input itself does not count. And every nested function call occupies memory until it returns, which is why deep recursion can run out of room and stop.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
O(1) extra space
let best = nums[0];
for (const n of nums) {
if (n > best) best = n;
}
return best;One variable, whatever the size of the list.
O(n) extra space
const seen = new Set();
for (const n of nums) {
if (seen.has(n)) return true;
seen.add(n);
}The Set can grow to hold every item. That is the price of the speed.
the memory you did not declare
function count(n) {
if (n === 0) return 0;
return 1 + count(n - 1); // this call waits for the next one
}
count(10); // 10 waiting calls - fine
count(100000); // RangeError: Maximum call stack size exceededMeasured: the stack gave out at roughly 8,800 calls. The exact figure varies by browser.
↑ play a little first, then dig in