Auxiliary Space vs Total Space
What You'll Learn
You'll learn the important distinction between auxiliary space (the extra memory your algorithm uses) and total space (all memory including the input).
The Core Idea
When analyzing space complexity, we can measure memory usage in two ways:
Total Space is the sum of all memory your algorithm uses—both the input data and any extra memory needed during execution.
Auxiliary Space is only the extra memory your algorithm allocates beyond the input itself. It excludes the input but includes temporary variables, call stack frames, and any additional data structures you create.
Think of it like cooking: If you're making a cake, the total space on your counter includes both the ingredients you started with (input) and all the bowls, mixers, and pans you need (auxiliary). The auxiliary space is just those extra tools—not counting the ingredients themselves.
Why the Distinction Matters
When we say an algorithm uses "O(1) auxiliary space," we mean it only needs a constant amount of extra memory, regardless of input size. The input might be huge, but we're not creating proportionally large temporary structures.
For example, reversing an array in-place uses O(1) auxiliary space (just a few swap variables) but O(n) total space (the array itself plus those variables).
In contrast, copying an array to reverse it uses O(n) auxiliary space because you create a whole new array.
Most of the time in algorithm analysis, when people discuss space complexity, they're referring to auxiliary space—the extra memory overhead your solution adds.
Key Takeaway: Auxiliary space measures only the extra memory your algorithm needs beyond the input, while total space includes everything. Understanding this distinction helps you accurately describe an algorithm's memory efficiency.