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.
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 exceeded

Measured: the stack gave out at roughly 8,800 calls. The exact figure varies by browser.

↑ play a little first, then dig in