Space Complexity Quiz
Three short prompts on space accounting: stack vs heap usage, recursion depth, and an in-place vs out-of-place comparison.
Question Bank
Easy
JavaScript
3 questions
space-complexity
asymptotic-analysis
quiz
fundamentals
393 views
6
What is the space complexity (extra space beyond the input) of this function and why?
Examples
Example 1:
Input: n = 12345
Output: 15
Explanation: 1 + 2 + 3 + 4 + 5 = 15. Only two scalars (sum and n) live across iterations regardless of input size, so extra space is O(1). Time is O(log n) because each step strips one decimal digit.function sumDigits(n) {
let sum = 0;
while (n > 0) {
sum += n % 10;
n = Math.floor(n / 10);
}
return sum;
}Implement an iterative version of the function below. State the space complexity of both the recursive and the iterative version.
Examples
Example 1:
Input: n = 100
Output: 5050
Explanation: The iterative version uses O(1) extra space (only i and total persist) versus O(n) stack frames for the recursive form. Both run in O(n) time, but the iterative shape is the safe production choice.function sumTo(n) {
if (n <= 0) return 0;
return n + sumTo(n - 1);
}Spot the space waste. The function should reverse arr in O(1) extra space, but it allocates O(n) on top.
Examples
Example 1:
Input: arr = [1, 2, 3, 4]
Output: arr mutates to [4, 3, 2, 1] and is returned
Explanation: The buggy reverse allocates a fresh out array, costing O(n) extra space. The in-place version swaps arr[lo] with arr[hi] while moving the pointers inward, using a single temporary slot, true O(1) extra space.function reverse(arr) {
const out = [];
for (let i = arr.length - 1; i >= 0; i--) {
out.push(arr[i]);
}
return out;
}