Space Complexity

Space complexity is the total memory an algorithm needs as a function of input size n. The detail exams test: the difference between total space and auxiliary space.

Total vs. auxiliary space

• Total space = input storage + auxiliary (extra) storage.
• Auxiliary space = only the extra memory the algorithm allocates — temporaries, copies, the recursion stack.
• When people say an algorithm is in-place, they mean O(1) auxiliary space, even though the input itself is O(n).

What counts as “extra”

• A fixed number of variables (i, j, temp) → O(1).
• A copy of the array, a visited[] map, a DP table → O(n), O(n²)… whatever its size.
• Recursion is never free: each active call holds a stack frame, so the space cost is the maximum depth of the call tree — linear recursion over n elements costs O(n) space even with no arrays in sight.

Worked contrasts (the exam favourites)

• Iterative sum of an array: O(1) auxiliary. Recursive sum: O(n) — same time, different space.
• Merge sort: O(n) auxiliary for the merge buffer (+O(log n) stack). Quick sort: O(log n) average stack, O(n) worst case — a repeat GATE question.
• Fibonacci: naive recursion O(n) stack depth; the two-variable iterative version is O(1).

Key takeaways

• State which measure you’re giving — “O(n) total, O(1) auxiliary” is a complete answer; “O(1)” alone can be marked wrong.
• Count the recursion stack every time you see a recursive call.
• Time can often be bought with space (memoisation) — that trade-off framing returns in the DP lessons.