Q2Design and Analysis of Algorithms
Question
2 marks
What is Space Complexity?
Answer
Space Complexity is the amount of memory an algorithm uses as a function of input size.
Space Complexity is the measure of the amount of working storage (memory) an algorithm requires as a function of the size of the input n. It includes both the space needed for the input data and the auxiliary space used by the algorithm during execution.
Space complexity is expressed using asymptotic notations. Example: Merge Sort requires O(n) auxiliary space for temporary arrays; Binary Search (iterative) requires O(1) auxiliary space; DFS uses O(V) space for the stack. It is as important as time complexity in resource-constrained systems.