Question Bank
Space Complexity Quiz
Difficulty: Easy
Three short prompts on space accounting: stack vs heap usage, recursion depth, and an in-place vs out-of-place comparison.
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
392 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.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.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.