Space Complexity
💠 Space Complexity — GATE-Level MCQs (Algorithms)
Q1. What is the auxiliary space used by merge sort for sorting an array of size n?
A) O(1) B) O(log n) C) O(n) D) O(n log n)
✅ Answer: C
Explanation: Merge Sort requires an auxiliary array of size n for merging → O(n).
Q2. The auxiliary space of Quick Sort (average case) equals:
A) O(n) B) O(log n) C) O(n log n) D) O(1)
✅ Answer: B
Explanation: Expected recursion-stack depth ≈ log n → O(log n) auxiliary space.
Q3. For recursive binary search, the space complexity is:
A) O(n) B) O(log n) C) O(1) D) O(n log n)
✅ Answer: B
Explanation: Recursion depth ≈ log n → O(log n) stack frames.
Q4. Iterative binary search requires what additional space?
A) O(1) B) O(log n) C) O(n) D) O(n log n)
✅ Answer: A
Explanation: Only index variables maintained → constant space.
Q5. Space complexity of depth-first search using adjacency list representation:
A) O(V + E) B) O(V²) C) O(E) D) O(V log V)
✅ Answer: A
Explanation: Stack + visited array → O(V + E).
Q6. Which algorithm requires more auxiliary space?
A) Merge Sort B) Quick Sort C) Heap Sort D) Insertion Sort
✅ Answer: A
Explanation: Merge Sort uses extra array O(n); others are in-place.
Q7. Space complexity of storing adjacency matrix for an undirected graph with V vertices:
A) O(V) B) O(V²) C) O(E) D) O(V + E)
✅ Answer: B
Explanation: Matrix has V×V entries → O(V²).
Q8. Space needed by an iterative Fibonacci algorithm storing only last two numbers:
A) O(1) B) O(n) C) O(log n) D) O(n²)
✅ Answer: A
Explanation: Only two variables maintained → constant auxiliary space.
Q9. Recursive factorial implementation uses how much extra space?
A) O(n) B) O(log n) C) O(1) D) O(n²)
✅ Answer: A
Explanation: One frame per recursive call → O(n).
Q10. Dynamic programming solution of Fibonacci (bottom-up) uses:
A) O(1) B) O(n) C) O(log n) D) O(2ⁿ)
✅ Answer: B
Explanation: DP table stores all n values → O(n) space.
Q11. The auxiliary space of an in-place Heap Sort is:
A) O(n) B) O(log n) C) O(1) D) O(n log n)
✅ Answer: C
Explanation: Percolation done inside array → constant space.
Q12. Space complexity of Breadth-First Search (BFS) for dense graph (V ≈ E):
A) O(V) B) O(V + E) C) O(V²) D) O(log V)
✅ Answer: B
Explanation: Queue + visited array → O(V + E).
Q13. What is the total space complexity of Merge Sort (including input)?
A) O(n) B) O(2n) C) O(n log n) D) Θ(n)
✅ Answer: D
Explanation: Input O(n) + Auxiliary O(n) = Θ(n).
Q14. Which algorithm’s space complexity changes with recursion depth?
A) Iterative Quick Sort B) Recursive Quick Sort C) Bubble Sort D) Selection Sort
✅ Answer: B
Explanation: Recursion depth varies → space ∝ stack depth.
Q15. For matrix multiplication of n×n matrices using standard triple loop, space = ?
A) O(n) B) O(n²) C) O(n³) D) O(log n)
✅ Answer: B
Explanation: Three matrices of size n² → O(n²) space.
Q16. Tower of Hanoi recursion for n disks uses ?
A) O(n) B) O(2ⁿ) C) O(log n) D) O(1)
✅ Answer: A
Explanation: Depth n recursion → O(n) stack frames.
Q17. Space complexity of storing a binary tree with n nodes using linked representation:
A) O(n) B) O(n log n) C) O(n²) D) O(log n)
✅ Answer: A
Explanation: Each node stores constant-size links → linear space.
Q18. For backtracking N-Queens (n×n), auxiliary space is:
A) O(n²) B) O(n) C) O(log n) D) O(1)
✅ Answer: B
Explanation: One recursive call per row → O(n) stack depth.
Q19. Space for dynamic programming LCS of strings of length m and n:
A) O(m + n) B) O(m n) C) O(m log n) D) O(1)
✅ Answer: B
Explanation: DP table of m×n → O(mn) space.
Q20. Optimized LCS (using only two rows) reduces space to:
A) O(m n) B) O(min(m,n)) C) O(m + n) D) O(1)
✅ Answer: B
Explanation: Store only two rows → O(min(m,n)) space.
Q21. Which sorting algorithm definitely not in-place?
A) Quick Sort B) Heap Sort C) Merge Sort D) Insertion Sort
✅ Answer: C
Explanation: Needs extra buffer → not in-place.
Q22. Space complexity of Floyd–Warshall algorithm for shortest paths:
A) O(V) B) O(V²) C) O(E) D) O(V + E)
✅ Answer: B
Explanation: Distance matrix → V×V → O(V²).
Q23. The recursion stack in DFS can grow up to:
A) O(E) B) O(V) C) O(V + E) D) O(log V)
✅ Answer: B
Explanation: One frame per vertex → O(V).
Q24. Auxiliary space of iterative factorial (loop version):
A) O(1) B) O(n) C) O(log n) D) O(n²)
✅ Answer: A
Explanation: Only accumulator variable → constant space.
Q25. Space complexity of recursive binary tree traversal (in-order):
A) O(log n) B) O(n) C) O(1) D) O(n log n)
✅ Answer: A
Explanation: Stack depth equals tree height ≈ log n → O(log n).
Q26. For skewed binary tree, recursion depth becomes:
A) O(log n) B) O(1) C) O(n) D) O(n log n)
✅ Answer: C
Explanation: Skewed height ≈ n → O(n) space.
Q27. Dijkstra’s algorithm (using array) space complexity = ?
A) O(V²) B) O(V + E) C) O(V log V) D) O(V)
✅ Answer: B
Explanation: Distance + visited arrays + graph → O(V + E).
Q28. When recursion is converted to iteration using an explicit stack, space complexity:
A) Remains same order B) Decreases C) Increases D) Becomes constant
✅ Answer: A
Explanation: Implicit call stack replaced by explicit one → same O(n).
Q29. Space complexity of storing a sparse n×n matrix with k non-zero entries:
A) O(n²) B) O(k) C) O(n) D) O(k log n)
✅ Answer: B
Explanation: Store only k entries → O(k).
Q30. Space complexity of recursive computation of nth Fibonacci (without memoization):
A) O(n) B) O(2ⁿ) C) O(log n) D) O(n²)
✅ Answer: A
Explanation: Tree height ≈ n → stack O(n); exponential time, not space.
💠 Space Complexity MCQs (continued)
Q31. The auxiliary space used by an iterative linear search is:
A) O(1) B) O(n) C) O(log n) D) O(n²)
✅ Answer: A
Explanation: Only loop variables used → constant space.
Q32. Recursive linear search has space complexity:
A) O(1) B) O(n) C) O(log n) D) O(n log n)
✅ Answer: B
Explanation: Each call adds a frame → O(n).
Q33. Space complexity of Kruskal’s algorithm (using union-find):
A) O(V + E) B) O(E log V) C) O(V²) D) O(E)
✅ Answer: A
Explanation: Union-find structure + edge list → O(V + E).
Q34. In DFS using recursion, if the graph is disconnected, maximum recursion depth is:
A) O(V) B) O(E) C) O(log V) D) O(V + E)
✅ Answer: A
Explanation: Each component explored separately → still ≤ V frames.
Q35. For dynamic programming 0/1 Knapsack, space complexity = ?
A) O(W) B) O(nW) C) O(n + W) D) O(n log W)
✅ Answer: B
Explanation: DP table n×W → O(nW) space.
Q36. Optimized knapsack (using 1D array) reduces space to:
A) O(n) B) O(W) C) O(1) D) O(nW)
✅ Answer: B
Explanation: Single array of capacity size → O(W).
Q37. Recursive Fibonacci (without memoization) time is exponential but space is:
A) O(2ⁿ) B) O(n) C) O(log n) D) O(1)
✅ Answer: B
Explanation: Only call-stack depth = n.
Q38. Space complexity of storing n keys in a hash table (open addressing):
A) O(n) B) O(n²) C) O(log n) D) O(n + log n)
✅ Answer: A
Explanation: Single array of size proportional to n.
Q39. Space complexity of storing n keys in a hash table (chaining):
A) O(n) B) O(n + m) C) O(m) D) O(n log n)
✅ Answer: B
Explanation: Array + linked lists → O(m + n).
Q40. Recursive Tower of Hanoi function for n disks consumes how much stack space?
A) O(log n) B) O(n) C) O(2ⁿ) D) O(n log n)
✅ Answer: B
Explanation: Each level adds a frame → O(n).
Q41. Iterative implementation of factorial reduces space to:
A) O(1) B) O(n) C) O(n²) D) O(log n)
✅ Answer: A
Explanation: Single accumulator → constant space.
Q42. Recursive inorder traversal on a skewed tree of n nodes requires:
A) O(log n) B) O(n) C) O(1) D) O(n²)
✅ Answer: B
Explanation: Height = n → stack O(n).
Q43. The space complexity of Prim’s algorithm using adjacency matrix:
A) O(V²) B) O(V + E) C) O(V log V) D) O(E)
✅ Answer: A
Explanation: Matrix + key/parent arrays → O(V²).
Q44. Using adjacency list representation, Dijkstra’s algorithm (with binary heap) needs:
A) O(V + E) B) O(V²) C) O(E log V) D) O(log E)
✅ Answer: A
Explanation: Storage for heap, adjacency list, and distances → O(V + E).
Q45. The recursion stack for Merge Sort reaches a maximum depth of:
A) O(log n) B) O(n) C) O(n log n) D) O(√n)
✅ Answer: A
Explanation: Divide until 1-element subarrays → log n levels.
Q46. The auxiliary array in Merge Sort adds space of:
A) O(log n) B) O(n) C) O(n log n) D) O(1)
✅ Answer: B
Explanation: One temporary array of n elements.
Q47. The recursion depth of Quick Sort (best case) is:
A) O(log n) B) O(n) C) O(n log n) D) O(1)
✅ Answer: A
Explanation: Balanced partitioning → depth log n.
Q48. In the worst case (already sorted), recursion depth of Quick Sort becomes:
A) O(1) B) O(log n) C) O(n) D) O(n log n)
✅ Answer: C
Explanation: Pivot chosen poorly → chain recursion → O(n).
Q49. Space complexity of recursive computation of GCD using Euclid’s algorithm:
A) O(n) B) O(log n) C) O(1) D) O(n²)
✅ Answer: B
Explanation: Depth proportional to log n divisions.
Q50. Dynamic programming for matrix chain multiplication uses:
A) O(n²) B) O(n³) C) O(n⁴) D) O(n log n)
✅ Answer: A
Explanation: DP table (i,j) of size n² → O(n²) space.
Q51. Bellman–Ford algorithm for V vertices and E edges uses:
A) O(V + E) B) O(VE) C) O(V²) D) O(E)
✅ Answer: A
Explanation: Distance array + edge list → O(V + E).
Q52. Storing adjacency matrix for directed weighted graph with V vertices:
A) O(V²) B) O(V + E) C) O(V log V) D) O(E)
✅ Answer: A
Explanation: Always V×V entries → O(V²).
Q53. For recursive binary tree height function, space complexity = ?
A) O(n) B) O(log n) C) O(h) D) O(1)
✅ Answer: C
Explanation: Depth = height h → O(h) stack.
Q54. Storing n elements in a max-heap requires:
A) O(log n) B) O(n) C) O(n²) D) O(1)
✅ Answer: B
Explanation: Single array of n elements.
Q55. The auxiliary space of heapify() on n elements = ?
A) O(1) B) O(log n) C) O(n) D) O(n log n)
✅ Answer: B
Explanation: Recursion depth equal to tree height log n.
Q56. The stack used in converting recursion to iteration consumes:
A) O(1) B) O(n) C) O(log n) D) O(n²)
✅ Answer: B
Explanation: Stores same number of frames explicitly → O(n).
Q57. Space complexity of topological sorting (using DFS):
A) O(V + E) B) O(V²) C) O(V log V) D) O(V)
✅ Answer: A
Explanation: DFS stack + visited array + adjacency → O(V + E).
Q58. For bubble sort on array of size n, auxiliary space = ?
A) O(1) B) O(log n) C) O(n) D) O(n log n)
✅ Answer: A
Explanation: In-place swapping → constant space.
Q59. Space complexity of recursive quickselect algorithm = ?
A) O(n) B) O(log n) C) O(1) D) O(n²)
✅ Answer: B
Explanation: Average depth of recursion = log n.
Q60. The recursion depth for DFS on a complete binary tree of n nodes:
A) O(n) B) O(log n) C) O(1) D) O(n²)
✅ Answer: B
Explanation: Height ≈ log n → stack O(log n).
Q61. Space complexity of radix sort for n numbers with d digits:
A) O(n + d) B) O(n) C) O(n + k) D) O(n + log d)
✅ Answer: C
Explanation: Uses counting array of size k + input array → O(n + k).
Q62. Counting sort on range [0, k] uses space:
A) O(n) B) O(k + n) C) O(k) D) O(log n)
✅ Answer: B
Explanation: Input array + count array → O(k + n).
Q63. Dynamic programming for edit distance (length m, n) uses:
A) O(m + n) B) O(mn) C) O(m log n) D) O(n²)
✅ Answer: B
Explanation: 2D DP table → O(mn).
Q64. Optimized edit distance (using two rows) reduces to:
A) O(m + n) B) O(min(m,n)) C) O(mn) D) O(1)
✅ Answer: B
Explanation: Keep two rows → O(min(m,n)).
Q65. Space complexity of recursive DFS on tree with height h:
A) O(n) B) O(h) C) O(1) D) O(log n)
✅ Answer: B
Explanation: Stack depth equals height.
Q66. For Floyd–Warshall, number of memory cells used ≈ ?
A) V B) V² C) V³ D) E
✅ Answer: B
Explanation: Stores distance matrix → O(V²).
Q67. Iterative approach of Fibonacci uses:
A) O(1) space B) O(n) C) O(log n) D) O(n²)
✅ Answer: A
Explanation: Stores only last two numbers.
Q68. For recursion tree of merge sort, total memory used simultaneously is:
A) O(n log n) B) O(n) C) O(log n) D) O(1)
✅ Answer: B
Explanation: Each recursion level releases space after merging.
Q69. In backtracking Sudoku solver, space used = ?
A) O(1) B) O(9⁹) C) O(n²) D) O(n³)
✅ Answer: C
Explanation: 9×9 board stored → O(n²).
Q70. Recursive Tower of Hanoi with memoization changes space from O(n) to:
A) O(1) B) O(2ⁿ) C) O(n) D) O(log n)
✅ Answer: C
Explanation: Memo table doesn’t reduce recursion depth.
Q71. Storing a trie with total k characters needs space:
A) O(k) B) O(k log k) C) O(n) D) O(k²)
✅ Answer: A
Explanation: Each node stores one char → O(k).
Q72. Space complexity of quicksort using tail-call optimization:
A) O(log n) B) O(n) C) O(1) D) O(n log n)
✅ Answer: A
Explanation: Tail call reduces half recursion depth → O(log n).
Q73. Recursive DFS on binary tree with height h and n nodes:
A) O(n) B) O(h) C) O(log n) D) O(1)
✅ Answer: B
Explanation: Depth determines stack space.
Q74. For breadth-first traversal on tree of n nodes:
A) O(n) B) O(log n) C) O(1) D) O(n²)
✅ Answer: A
Explanation: Queue may hold up to n/2 nodes → O(n).
Q75. The space complexity of recursive binary search tree insertion is:
A) O(h) B) O(n) C) O(1) D) O(log n)
✅ Answer: A
Explanation: One frame per height level.
Q76. Dynamic programming for subset sum problem uses:
A) O(S) B) O(nS) C) O(n) D) O(n log S)
✅ Answer: B
Explanation: Table of size n×S → O(nS).
Q77. Optimized subset sum (1D array) reduces space to:
A) O(S) B) O(nS) C) O(n) D) O(1)
✅ Answer: A
Explanation: Single array of size sum.
Q78. Space complexity of recursive merge sort ignoring input = ?
A) O(n) B) O(log n) C) O(n log n) D) O(1)
✅ Answer: A
Explanation: Temporary array + recursion → O(n).
Q79. DFS using explicit stack instead of recursion changes space to:
A) O(V) B) O(V + E) C) O(E) D) O(log V)
✅ Answer: A
Explanation: Stack stores visited vertices → O(V).
Q80. Recursive binary search space for array of size 2048 = ?
A) 11 frames B) 2048 frames C) log₂2048 frames D) √2048 frames
✅ Answer: C
Explanation: Depth = log₂2048 = 11 → O(log n).
Q81. Dynamic programming TSP uses space:
A) O(n²) B) O(n·2ⁿ) C) O(2ⁿ) D) O(n³)
✅ Answer: B
Explanation: DP table indexed by subset and vertex → O(n·2ⁿ).
Q82. Space complexity of storing adjacency list for tree with n nodes:
A) O(n) B) O(n + E) C) O(n²) D) O(1)
✅ Answer: A
Explanation: Tree has E = n−1 → O(n + n−1) = O(n).
Q83. In quicksort with random pivot, expected stack space = ?
A) O(n) B) O(log n) C) O(n log n) D) O(1)
✅ Answer: B
Explanation: Random pivot ensures balanced recursion.
Q84. Space complexity of storing disjoint sets using array of size n = ?
A) O(n) B) O(log n) C) O(n log n) D) O(1)
✅ Answer: A
Explanation: Parent array size n.
Q85. The auxiliary space for recursion in computing factorial(25) = ?
A) O(1) B) O(25) C) O(log 25) D) O(2²⁵)
✅ Answer: B
Explanation: Depth = n = 25 → O(n).
Q86. Recursive Fibonacci(10) stack depth = ?
A) 10 B) 5 C) 2¹⁰ D) log₁₀
✅ Answer: A
Explanation: Depth proportional to n → 10 frames.
Q87. BFS for sparse graph (E ≈ V) requires:
A) O(V) B) O(V + E) C) O(V log V) D) O(E²)
✅ Answer: B
Explanation: Queue + adjacency → O(V + E).
Q88. Space complexity of recursive binary tree leaf count = ?
A) O(h) B) O(n) C) O(1) D) O(log n)
✅ Answer: A
Explanation: Stack height = tree height.
Q89. For iterative preorder traversal using stack, space = ?
A) O(h) B) O(n) C) O(log n) D) O(1)
✅ Answer: A
Explanation: Stack holds nodes along one path.
Q90. Space complexity of storing AVL tree with n nodes = ?
A)
O(log n) B) O(n) C) O(n²) D) O(1)
✅ Answer: B
Explanation: Each node has constant fields.
Q91. Space complexity of memoized Fibonacci(n) = ?
A) O(n) B) O(log n) C) O(n²) D) O(1)
✅ Answer: A
Explanation: Memo array stores n computed values.
Q92. For recursive GCD(100, 25), maximum depth ≈ ?
A) O(1) B) O(log n) C) O(n) D) O(25)
✅ Answer: B
Explanation: Depth ≈ log(min(a,b)).
Q93. Space complexity of DFS on complete graph of n vertices = ?
A) O(n) B) O(n²) C) O(n log n) D) O(1)
✅ Answer: A
Explanation: Stack ≤ n vertices → O(n).
Q94. Dynamic programming coin change problem uses:
A) O(nS) B) O(S) C) O(n²) D) O(log n)
✅ Answer: A
Explanation: Table with n coins × sum S.
Q95. Optimized coin change (1D DP) uses:
A) O(S) B) O(nS) C) O(1) D) O(n)
✅ Answer: A
Explanation: Only 1D array of sum size.
Q96. The space complexity of storing adjacency matrix for graph with 20 vertices:
A) 20 B) 400 C) O(V²) D) O(V + E)
✅ Answer: C
Explanation: n² entries → O(V²).
Q97. Storing disjoint sets using linked lists (n elements, k sets) → space:
A) O(n + k) B) O(n) C) O(k) D) O(n log k)
✅ Answer: A
Explanation: Each node stored once + k heads.
Q98. Dynamic programming for shortest path in DAG uses:
A) O(V + E) B) O(V²) C) O(V log V) D) O(E²)
✅ Answer: A
Explanation: Only distance array + adjacency → O(V + E).
Q99. For recursion elimination using explicit stack in inorder traversal:
A) O(h) B) O(n) C) O(1) D) O(log n)
✅ Answer: A
Explanation: Stack holds one path → O(h).
Q100. Space complexity of storing binary min-heap of 1024 elements:
A) 1024 B) O(n) C) O(log n) D) O(1)
✅ Answer: B
Explanation: Stored in single array → O(n).
About the Author
